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