题意：给定两个长度为n(n<=2000)的由0和1组成的字符串A和B，有三种操作
1：将A向左循环移一格
2：将B向右循环移一格
3：将一个b[i]为1的位置的a[i]改为(1 - a[i])
询问将A变为B的最短操作次数。若A无法变为B，则输出-1。
输入描述：两行，每行一个长度为n的只包含0和1的字符串
输出描述：一行，一个整数表示最小的的操作次数.若无法从A变为B，则输出-1.
输入样例：
1010
1100
输出样例：
3
解析：首先先判断-1的情况，不难发现如果B全为0且A也全为0，那么就输-1。如果B全为0且A也全为0，那么答案就是0。
再来看看如何计算答案。用L[i]表示A中第i个位置向左移多少个位置后才能在B中有一个1。R[i]表示A中第i个位置向右移多少个位置后在B中有1。
枚举最终的结果A的状态（即移动到了哪个位置），这样进行修改操作的次数是固定的（A与B中每位不同的个数就是修改的次数）。
由上一步可以得出枚举的状态是由原状态左移（或右移）几个单位得到的，假设这个值是cnt。
以左移为例。对于每个点的L[i]，如果L[i] <= cnt，那么就不会产生多余的移动操作。可是若L[i] > cnt，那么这个点可能由原位置向右移u个单位，再向左移动u+L[i]*2-cnt个单位的过程中更改的；也可能是在原位置向左移L[i]个单位后再向右移L[i]-cnt个单位的过程中更改的。所以对于每个点，它的值要么是 向右的最大值*2+向左的最大值*2-cnt；要么是 向左的最大值*2-cnt,从中取一个最小值即可。
对于右也是类似的操作。具体实现细节看代码。
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn=2005; 7 int n,L[maxn],R[maxn],bj[maxn],mx,mi,ans; 8 int tota,totb,len,que[maxn]; 9 char a[maxn],b[maxn]; 10 11 int cmpL(int a,int b) { 12 return L[a]<L[b]; 13 } 14 15 int cmpR(int a,int b) { 16 return R[a]<R[b]; 17 } 18 19 int main() { 20 scanf("%s%s",a+1,b+1); n=strlen(a+1); 21 ans=2e9; 22 for (int i=1;i<=n;++i) { //求1的个数 23 if (a[i]=='1') tota++; 24 if (b[i]=='1') totb++; 25 } 26 if (!totb) { //判-1 27 if (!tota) return puts("0"),0; 28 return puts("-1"),0; 29 } 30 for (int i=1;i<=n;++i) { //预处理L[i]与R[i] 31 int ind=i,cnt=0; 32 while (b[ind]!='1') { 33 ind--; cnt++; 34 if (ind==0) ind=n; 35 } 36 L[i]=cnt; 37 ind=i; cnt=0; 38 while (b[ind]!='1') { 39 ind++; cnt++; 40 if (ind==n+1) ind=1; 41 } 42 R[i]=cnt; 43 } 44 for (int i=1;i<=n;++i) { //枚举移动后左端点的最终位置 45 int ind,sum=0; //sum记录需要修改的点的个数 46 if (i==1) ind=1; else ind=n-i+2; 47 for (int j=1;j<=n;++j) bj[j]=0; //bj[i]记录i号点是否要修改 48 for (int j=1;j<=n;++j) { 49 if (a[ind]!=b[j]) sum++,bj[ind]=1; 50 ind++; if (ind>n) ind=1; 51 } 52 int cnt; //cnt表示向左移(或右移)的位数 53 if (i==1) cnt=0; else cnt=n-i+1; //cnt表示向左移的位数 54 len=0; 55 for (int j=1;j<=n;++j) 56 if (bj[j] && L[j]>cnt) que[++len]=j; 57 sort(que+1,que+1+len,cmpR); 58 mx=0; mi=2e9; 59 if (len>0) mi=min(mi,R[que[len]]*2+cnt); 60 for (int j=len;j>=1;--j) { 61 mx=max(mx,L[que[j]]); 62 if (j>1) mi=min(mi,R[que[j-1]]*2+mx*2-cnt); 63 } 64 if (len>0) mi=min(mi,mx*2-cnt); 65 if (!len) mi=cnt; 66 ans=min(ans,mi+sum); 67 cnt=i-1; len=0; //cnt表示向右移的位数 68 for (int j=1;j<=n;++j) 69 if (bj[j] && R[j]>cnt) que[++len]=j; 70 sort(que+1,que+1+len,cmpL); 71 mx=0; mi=2e9; 72 if (len>0) mi=min(mi,L[que[len]]*2+cnt); 73 for (int j=len;j>=1;--j) { 74 mx=max(mx,R[que[j]]); 75 if (j>1) mi=min(mi,L[que[j-1]]*2+mx*2-cnt); 76 } 77 if (len>0) mi=min(mi,mx*2-cnt); 78 if (!len) mi=cnt; 79 ans=min(ans,mi+sum); 80 } 81 printf("%d",ans); 82 return 0; 83 }
转载于:https://www.cnblogs.com/Gaxc/p/9839067.html
相关资源：JAVA上百实例源码以及开源项目