E. Moving Chips

题目大意：

2*n的棋盘上有若干棋子，每次可以选择任意一颗移动。问吃掉棋盘上所有棋子的最小步数是多少。

思路和代码：

麻了，最后剩十分钟做这个，还理解错题意了

首先，贪心去想肯定不把把两边全空的格子计入考虑。

我一开始理解成只能移动其中一颗棋子了，但是是每次都可以随意移动的。区别就在于下图：

考虑状态方程定义：dp[i,1/2]表示前面所有的棋子都吃完后剩下来的那颗棋子在点(1/2,i)处所能得到的最小点数（最后的花费要减去1）.下面给出AC代码。

void solve2(){ 	cin >> n ; 	cin >> s[1] >> s[2] ; 	s[1] =   + s[1] ; 	s[2] =   + s[2] ; 	 	int l = 1 , r = n ; 	while(l <= n && s[1][l] == '.' && s[2][l] == '.') l ++ ; 	while(1 <= r && s[1][r] == '.' && s[2][r] == '.') r -- ; 	 	string t[3] = {} ; 	t[1] =   ; 	t[2] =   ; 	rep(i , l , r ) t[1] += s[1][i] ;  	rep(i , l , r ) t[2] += s[2][i] ;  	 	int m = t[1].size() - 1 ; 	 	vct<vct<ll> > dp(m + 1 , vct<ll>(5 , INF)) ; 	dp[0][1] = dp[0][2] = 0 ;  	rep(i , 1 , m){ 		if(t[1][i] == t[2][i] && t[1][i] == '*'){ 			dp[i][1] = min(dp[i - 1][1] + 2 , dp[i - 1][2] + 2) ; 			dp[i][2] = min(dp[i - 1][2] + 2 , dp[i - 1][1] + 2) ; 			continue ; 		}else if(t[1][i] == '*' && t[2][i] == '.'){ 			dp[i][1] = min(dp[i - 1][1] + 1 , dp[i - 1][2] + 2) ; 			dp[i][2] = min(dp[i - 1][2] + 2 , dp[i - 1][1] + 2) ; 		}else if(t[2][i] == '*' && t[1][i] == '.'){ 			dp[i][1] = min(dp[i - 1][1] + 2 , dp[i - 1][2] + 2) ; 			dp[i][2] = min(dp[i - 1][2] + 1 , dp[i - 1][1] + 2) ; 		}else{ 			dp[i][1] = min(dp[i - 1][1] + 1 , dp[i - 1][2] + 2) ; 			dp[i][2] = min(dp[i - 1][2] + 1 , dp[i - 1][1] + 2) ; 		} 		 	} //	cout << t[1] << \n << t[2] << \n ; //	rep(i , 1 , 2) //	rep(j , 1 , m) cout << dp[j][i] <<  \n[j == m] ; 	 	cout << min(dp[m][1] , dp[m][2]) - 1 << \n ; } 

小结：

很棒的dp题啊，下面给出我错误理解题意写出的代码，供大家笑笑

void solve(){ 	cin >> n ; 	cin >> s[1] >> s[2] ; 	s[1] =   + s[1] ; 	s[2] =   + s[2] ; 	 	int l = 1 , r = n ; 	while(l <= n && s[1][l] == '.' && s[2][l] == '.') l ++ ; 	while(1 <= r && s[1][r] == '.' && s[2][r] == '.') r -- ; 	 	string t[3] = {} ; 	t[1] =   ; 	t[2] =   ; 	rep(i , l , r ) t[1] += s[1][i] ;  	rep(i , l , r ) t[2] += s[2][i] ;  	 	int m = t[1].size() - 1 ; 	 	vct<vct<ll> > dp(m + 1 , vct<ll>(5 , INF)) ; 	dp[0][1] = dp[0][2] = 0 ;  	rep(i , 1 , m){ 		if(t[1][i] == '*' && t[2][i] == '.'){ 			dp[i][1] = min(dp[i - 1][1] + 1 , dp[i - 1][2] + 2) ; 		}else if(t[1][i] == '.' && t[2][i] == '*'){ 			dp[i][2] = min(dp[i - 1][2] + 1 , dp[i - 1][1] + 2) ; 		}else if(t[1][i] == '.' && t[2][i] == '.'){ 			dp[i][1] = min(dp[i - 1][1] + 1 , dp[i - 1][2] + 2 ) ; 			dp[i][2] = min(dp[i - 1][2] + 1 , dp[i - 1][1] + 2 ) ; 		}else{ 			ll row1 = min(dp[i - 1][1] + 1 , dp[i - 1][2] + 2) ; 			ll row2 = min(dp[i - 1][2] + 1 , dp[i - 1][1] + 2) ; 			dp[i][1] = row2 + 1 ; 			dp[i][2] = row1 + 1 ; 		} 	} 	 	rep(i , 1 , 2) 	rep(j , 1 , m) cout << dp[j][i] <<  \n[j == m] ; 	 	cout << min(dp[m][1] , dp[m][2]) - 1 << \n ; 	 }//code_by_tyrii