#C240220D. 翻转

前言（Front talk)

知道是动态规划，但是还是不会做。甚至没有想出来应该怎么设。

网址（Website）

题目详情 - 翻转 - Super

题解 - 翻转 - Super

题解（Solution）

思路：

部分分给了一个的情况，我们可以分类讨论。

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

特判：

如果为奇数，那么一定不能使串变为串，直接输出。

对于：

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

对于：

首先，操作可以个用操作代替，因此；

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

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

初始意为不用操作需要消耗的代价，有：

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

奇数个的时候，既可以由直接转换过来，不需要考虑配对，也可以由加上使用操作带来的贡献转换，意为将和用操作配对。

偶数个的时候，需要考虑是否能和进行操作，因此会和有关，即当前的和前面的多出来的一个数进行操作匹配，其余的和奇数个一样。

总的来说，有：

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]));

注意：多测清空。

代码（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;
}