3
28
2016
0

环形问题 总结~

环形问题的两种处理方法:
1、倍增法:拆环为链,在原长度*2的链上操作
2、取余法:多用于数学问题 %MOD MOD为周期长度
 
几个栗子~
1、NOIP2006 T1能量项链Orz
第一种:
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		a[i+n]=a[i];//破环为链
	}
	memset(s,0,sizeof(s));
	for(i=1;i<n;i++)//i=已经合并的珠子的数目
		for(j=0;j<2*n-i;j++)//j表示起点
			for(k=j+1;k<=i+j;k++)//k表示从哪个地方合并
				s[j][i+j]=max(s[j][i+j],s[j][k-1]+s[k][i+j]+a[j]*a[k]*a[i+j+1]);
	for(i=0;i<n;i++)
		ans=max(ans,s[i][i+n-1]);//找到最优解

 

第二种:(变量名竟然不一样-。-)
	
	for(i=0;i<n;i++) {scanf("%d",&a[i]);};
	for(i=0;i<n;i++) f[i][2]=a[i]*a[(i+1)%n]*a[(i+2)%n];
	for(j=3;j<=n;j++)//长度 
		for(i=n-1;i>=0;i--)//起点 
			for(k=1;k<j;k++)//断开位置 
			{
				int t=f[i][k] + f[(i+k)%n][j-k] + a[i]*a[(i+j)%n]*a[(i+k)%n];
				if(f[i][j]<t) f[i][j]=t;
			}
	for(i=0;i<n;i++)
		if(f[i][n]>ans) ans=f[i][n];
 

 

2、今天做的一道题:
第一层:枚举旋转几个位置,
第二层:
关键:配对的珠子不交叉,否则一定可找到更优的方案(二分图思想!!)
故枚举B链开头(0号珠子)对应的A链珠子(标号)
第三层:枚举A链每个珠子,可得B链珠子位置,求和取最小
(注:研究对象为黑珠子)
void force()
{
	res=inf;
	for(int i=0;i<=n-1;i++){
		for(int j=0;j<=K-1;j++){
		int sum=0;
			for(int k=0;k<=K-1;k++){
				int pos=(b[(j+k)%K]-i+n)%n;//+n防止-i后出现负数 
				sum+=d(a[k],pos);
			}
			if(sum<res) res=sum; 
		}
	}
}

 

Category: 总结 | Tags: 数论 动态规划 乱搞 | Read Count: 468

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com