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