NC204121. 牛牛的01限定串
描述
输入描述
第一行输入五个整数n,,,, 。且保证
接下来输入两行表示字符串s,t,|s|=|t|=n
其中,s串完全由'0','1'组成,t串完全由'0','1','?'组成。
?表示损坏的部分,也就是需要你还原的部分。
输入数据保证t串中0的数目,1的数目,也就是至少存在一种合法填充t串中?的方案。
输出描述
请输出两个整数,表示还原后的最小得分与最高得分。
示例1
输入:
8 6 2 1 1 10110011 ????????
输出:
0 4
说明:
可以构造01串t="00011000"达到最小得分(与s串没有相似的前缀与后缀)
可以构造01串t="00000011"(4个相似的后缀)达到最大得分。
示例2
输入:
20 1 19 55 97 11111010101111111111 1?????1?1?1????????1
输出:
566 1439
说明:
示例3
输入:
1 0 1 -999 1000 0 ?
输出:
0 0
说明:
因为限制条件为必须有1个1,所以?处只能填1C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 8300K, 提交时间: 2020-05-08 23:49:58
#include<bits/stdc++.h> using namespace std; const int maxn = 1005; char s[maxn],t[maxn]; int mi[maxn][maxn],mx[maxn][maxn],sum[maxn]; int n,c0,c1,vp,vs; signed main(){ scanf("%d%d%d%d%d",&n,&c0,&c1,&vp,&vs); scanf("%s%s",s+1,t+1); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+s[i]-'0'; memset(mi,0x3f,sizeof(mi)); memset(mx,-0x3f,sizeof(mx)); mi[0][0] = mx[0][0] = 0; for(int i=1;i<=n;i++){ for(int j=0;j<=c1;j++){ if(t[i]!='1'){ mi[i][j]=min(mi[i][j],mi[i-1][j]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j)); mx[i][j]=max(mx[i][j],mx[i-1][j]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j)); } if(t[i]!='0' && j>0){ mi[i][j]=min(mi[i][j],mi[i-1][j-1]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j)); mx[i][j]=max(mx[i][j],mx[i-1][j-1]+vp*(sum[i]==j)+vs*(sum[n]-sum[i]==c1-j)); } } } if(sum[n]!=c1){ mi[n][c1]-=vs; mx[n][c1]-=vs; } cout<<mi[n][c1]<<' '<<mx[n][c1]<<endl; return 0; }
C++11(clang++ 3.9) 解法, 执行用时: 18ms, 内存消耗: 18524K, 提交时间: 2020-05-09 20:59:27
#include<bits/stdc++.h> using namespace std; int n,n0,n1,u,v; char s[1005],t[1005]; long long a[1005][1005],mi[1005][1005],mx[1005][1005]; bool ck(int &x,int &y){ if(x<0||x>n0||y<0||y>n1)return 0; return 1; } int main(){ scanf("%d%d%d%d%d",&n,&n0,&n1,&u,&v); scanf("%s%s",s,t); memset(mi,127,sizeof mi); memset(mx,-127,sizeof mx); int x=0,y=0; for(int i=0;i<n;++i){ if(s[i]=='0')++x; else ++y; if(ck(x,y))a[x][y]+=u; } x=n0,y=n1; for(int i=n-1;~i;--i){ if(s[i]=='0')--x; else --y; if(ck(x,y))a[x][y]+=v; } mi[n0][n1+1]=0,mx[n0][n1+1]=0; for(int i=n0;~i;--i) for(int j=n1;~j;--j){ if(t[i+j]=='?'){ mi[i][j]=min(mi[i+1][j],mi[i][j+1])+a[i][j]; mx[i][j]=max(mx[i+1][j],mx[i][j+1])+a[i][j]; } else if(t[i+j]=='0'){ mi[i][j]=mi[i+1][j]+a[i][j]; mx[i][j]=mx[i+1][j]+a[i][j]; } else{ mi[i][j]=mi[i][j+1]+a[i][j]; mx[i][j]=mx[i][j+1]+a[i][j]; } } printf("%lld %lld",mi[0][0],mx[0][0]); return 0; }