$#C240220D. 翻转

标签（Label）

• 动态规划

网址（Website）

$\qquad$ 题目详情 - 翻转 - Super

$\qquad$ 题解 - 翻转 - Super

题解（Solution）

思路：

$\qquad$部分分给了一个 $x>=y$ 的情况，我们可以分类讨论。

$\qquad$设 $tot$ 表示当前的两个字符串的不同地方的个数； $x$ 操作即为消费为 $x$ 的操作，$y$ 操作同理。

特判：

$\qquad$如果 $\ tot\ $ 为奇数，那么一定不能使 $a$ 串变为$\ b\ $串，直接输出 $\ -1\ $。

对于$\ x>=y\ $：

$\qquad$很明显，直接用 $y$ 操作一定是更优的，如果当前的 $\ tot>=4\ $ 那么我们一定可以找到一种只用 $\ y \ $ 的变化方式字符串 $\ a\ $ 变成 $\ b\ $ ，即 $\ ans=tot/2y\ $ 。而当 $\ tot==2\ $ 且两个不同点满足 $\ i+1= j\ $ 时，最终的答案 $ ans\ =\ min(2y,x)\ $ 。

对于 $\ x<y\ $ ：

$\qquad$首先，$x$ 操作可以 $2$ 个用 $\ y\ $ 操作代替，因此 $x=min(x,2*y)$；

$\qquad$我们求出 $a,b$ 字符串所有不同的地方，用 $pos[]$ 数组表示。根据样例一第一组解释我们可以想到想将两个不同点都变成与 $b$ 中一样的

$\qquad$这道题的数据范围提示用动态规划做，由于不知道要做多少次 $x$ 操作，不妨设 $f[i][j]$ 表示当前第 $i$ 个不同的地方，并且前面已经做了 $j$ 次 $x$ 操作。

$\qquad$初始 $f[i][0]$ 意为不用 $x$ 操作需要消耗的代价，有：$f[i][0]=i/2*y;$

$\qquad$对于当前的 $i$ ，我们分为两种情况，一种是当前的点的数量是偶数个的时候，一种是数量是奇数个的时候。

$\qquad$奇数个的时候， $f[i][j]$ 既可以由 $f[i-1][j]$ 直接转换过来，不需要考虑配对，也可以由 $f[i-2][j-1]$ 加上使用 $x$ 操作带来的贡献 $x*(pos[i]-pos[i-1])$ 转换，意为将 $i$ 和 $i-1$ 用 $x$ 操作配对。

$\qquad$偶数个的时候，$f[i][j]$ 需要考虑是否能和 $i-1$ 进行 $y$ 操作，因此 $f[i][j]$ 会和 $f[i-1][j]+y$ 有关，即当前的 $i$ 和前面的多出来的一个数进行 $y$ 操作匹配，其余的和奇数个一样。

$\qquad$总的来说，有：

$\qquad$$\qquad$if(i&1) f[i][j] = min(f[i-1][j] , f[i-2][j-1] + x*(pos[i]-pos[i-1]));

$\qquad$$\qquad$else f[i][j] = min(f[i-1][j] + y, f[i-2][j-1] + x*(pos[i]-pos[i-1]));

注意：多测清空。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5005;

int f[N][N],pos[N],tot;
int n,x,y,ans;

char s[N],t[N];
void Solve(){
	//输入 
	tot=0;cin>>n>>x>>y>>(s+1)>>(t+1);
	For(i,1,n) if(s[i] != t[i]) pos[++tot]=i;
	
	//特判 
	if(tot == 2 && pos[1]+1 == pos[2]) return cout<<min(2*y , x)<<'\n',void();
	if(tot & 1) return cout<<"-1\n",void();
	if(x >= y)  return cout<<tot/2*y<<'\n',void();
	
	x = min(2 * y , x);
	ans = tot/2 * y;//全部用y操作 
		
	For(i,0,tot) For(j,0,tot) f[i][j] = inf;//注意不要用memset,会超时 
		
	For(i,0,tot) f[i][0] = i/2 * y;//不用操作 x 时的消费 
	For(i,1,tot){//枚举到了第多少位 
		For(j,1,i/2){//配对了多少组
			if(i&1) f[i][j] = min(f[i-1][j] , f[i-2][j-1] + x*(pos[i]-pos[i-1]));
			else f[i][j] = min(f[i-1][j] + y, f[i-2][j-1] + x*(pos[i]-pos[i-1]));
		}
	} 
		
	For(i,1,tot/2) ans = min(ans, f[tot][i]);
	return cout<<ans<<'\n',void();
}

//多测清空 
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("flip");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	int T = input(),Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1024.,0;
}