环形问题的两种处理方法：
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;
}
}
}
评论 (0)
