SRM 589题解

250，500过段时间再补>_<

1000:

题意很简单，给定一个长度不超过300的二进制串,和整数m。有两种操作:1.将任意一位翻转 2:将前k*m(k为正整数)位翻转。两种操作代价均为1，求使得前L-m位和后L-m位相等的最小代价。

首先有个很显然的事情，如果确定了二进制串的前m位，那么整个二进制串就确定下来了,第1位和m+1,2*m+1...相等，第2位和m+2,2*m+2...相等，以此类推。k*m<=300,当k很小，m很大时，只需2^k枚举第二种操作中的k中操作是否进行即可；当k很大，m很小时，我们可以2^m枚举前m位，于是整个串就定下来了，我们可以通过从前向后DP求解，如果前i位已解决，后面的第二中操作将不会影响前面的正确性。

dp[j+k][0]表示搞定了j+k前面的所有位且第一段(1~m)与最终端相同，dp[j+k][1]表示搞定了j+k前面的所有位且第一段(1~m)与最终端相反。即可转移，代码如下:

代码链接

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std ; typedef long long LL ; const int N=1000; const double eps = 1e-8; bool rev[N],a[N]; int f[N][2]; class FlippingBitsDiv1{ public: int getmin(vector 
        
          S, int m){ int n=S.size(); string s; for(int i=0;i
         
          =0;--j){ f^=rev[j]; a[j]^=f; } for(int j=0;j
          
           >k)&1)) cnt1++;//different from the final else cnt2++; } f[j+m][0]=min(f[j][0]+cnt1,f[j][1]+cnt2+1);//first string is final string f[j+m][1]=min(f[j][0]+cnt1+1,f[j][1]+cnt2);//firsr string is reverse final string } ans=min(ans,f[j][0]); } } return ans; } };