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;
	}
};