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