solution

考虑dp。用表示对于t的前个位置,有个位置为1最小得分。

显然当前面1的个数确定之后,后面1的个数也确定了。也就是我们可以计算对于位置它的前缀是否和s相似,它的后缀是否和s相似,然后就可以计算出i位置的贡献。枚举i位置是'0'还是'1'转移即可。

code

/*
* @Author: wxyww
* @Date: 2020-05-08 20:02:22
* @Last Modified time: 2020-05-08 20:22:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int g[N][N],f[N][N],cnt[N],cc1[N],cc0[N];
char s[N],t[N];

int main() {
    int n = read(),c0 = read(),c1 = read(),vp = read(),vs = read();
    memset(f,0x3f,sizeof(f));
    memset(g,-0x3f,sizeof(g));

    scanf("%s",s + 1);
    scanf("%s",t + 1);

    for(int i = 1;i <= n;++i) cnt[i] = cnt[i - 1] + (s[i] == '1');
    g[0][0] = f[0][0] = (cnt[n] == c1) ? vs : 0;
    // for(int i = 1;i <=)
/*
    for(int i = n;i >= 1;--i) {
        cc1[i] = cc1[i + 1] + (t[i] == '1');
        cc0[i] = cc0[i + 1] + (t[i] == '0');
    }*/

    int n1 = 0;
    for(int i = 1;i <= n;++i) {
        n1 += (t[i] == '1');
        for(int j = n1;j <= c1;++j) {

            // if(cc1[i + 1] + j > c1) continue;

            // if(cc0[i + 1] + (i - j) > c0) continue;

            int k = 0;

            if(j == cnt[i]) {
                // if(i == 1 && j == 0) printf("%d\n",cnt[i]);
                k += vp;
            }

            if(c1 - j == cnt[n] - cnt[i] && i != n) {
                k += vs;
            }

            if(t[i] == '1') {
                if(j == 0) continue;
                f[i][j] = f[i - 1][j - 1] + k;
                g[i][j] = g[i - 1][j - 1] + k;
            }
            if(t[i] == '0') {
                f[i][j] = f[i - 1][j] + k;
                g[i][j] = g[i - 1][j] + k;
            }
            if(t[i] == '?') {
                g[i][j] = max(g[i - 1][j],g[i - 1][max(0,j - 1)]) + k;
                f[i][j] = min(f[i - 1][j],f[i - 1][max(0,j - 1)]) + k;
            }
        }

    }

    cout<<f[n][c1]<<" "<<g[n][c1]<<endl;

    return 0;
}