比赛 |
EYOI与SBOI开学欢乐赛10th |
评测结果 |
AAAAAAAAAA |
题目名称 |
01串 |
最终得分 |
100 |
用户昵称 |
ZRQ |
运行时间 |
0.240 s |
代码语言 |
C++ |
内存使用 |
98.66 MiB |
提交时间 |
2022-10-10 20:23:25 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<bitset>
#define ll long long
using namespace std;
const int N=5010;
int n;
ll x,y,cnt,pos[N],d[N],dp[N][N];
bitset<5010> a,b;
int main()
{
freopen("zerone.in","r",stdin);
freopen("zerone.out","w",stdout);
cin>>n>>x>>y>>a>>b;
x=min(x,2*y);
for(int i=0;i<n;++i)
if(a[i]!=b[i])
{
++cnt,pos[cnt]=i;
if(cnt>1) d[cnt-1]=pos[cnt]-pos[cnt-1];
}
if(cnt&1)
{
printf("-1\n");
return 0;
}
int r;
ll ans=(pos[cnt]-pos[1])*x;
for(int len=0;len<=(cnt-1)>>1;++len)
for(int l=1;l+len*2<=cnt-1;++l)
{
r=l+len*2+1;
if(l+1==r)
{
dp[l][r]=min(d[l]*x,y);
continue;
}
dp[l][r]=min(dp[l+1][r-1]+y,min(dp[l+2][r]+min(d[l]*x,y),dp[l][r-2]+min(d[r-1]*x,y)));
}
printf("%lld\n",dp[1][cnt]);
return 0;
}