把过程看作是从(0,0)到(c0,c1)的过程,1表示向右走,0表示向下走,
maxx【i】【j】表示i个0,j个1的最高得分
minn【i】【j】表示i个0,j个1的最低得分
sum【x】表示标准串s,到第x位置为止共有多少1
满足s与t前缀x1同等价于sum【x】==j,后缀x1+1~n同就等价于sum【n】-sum【x】==c1-j
当t的第pos位是1或者?,maxx【i】【j】可以从maxx【i】【j-1】向右移动得到(minn同)
(0或?同)
maxx[i][j]=max(maxx[i][j],maxx[i][j-1]+vp*(sum[pos]==j)+vs*(sum[n]-sum[pos]==c1-j)
minn[i][j]=min(minn[i][j],minn[i][j-1]+vp*(sum[pos]==j)+vs*(sum[n]-sum[pos]==c1-j))
maxx【i】【j】表示i个0,j个1的最高得分
minn【i】【j】表示i个0,j个1的最低得分
sum【x】表示标准串s,到第x位置为止共有多少1
满足s与t前缀x1同等价于sum【x】==j,后缀x1+1~n同就等价于sum【n】-sum【x】==c1-j
当t的第pos位是1或者?,maxx【i】【j】可以从maxx【i】【j-1】向右移动得到(minn同)
(0或?同)
maxx[i][j]=max(maxx[i][j],maxx[i][j-1]+vp*(sum[pos]==j)+vs*(sum[n]-sum[pos]==c1-j)
minn[i][j]=min(minn[i][j],minn[i][j-1]+vp*(sum[pos]==j)+vs*(sum[n]-sum[pos]==c1-j))
#include<bits/stdc++.h> using namespace std; const int N=1e3+10; int n,c0,c1,vp,vs,sum[N<<1],minn[N][N],maxx[N][N],pos; string s,t; int main(){ cin>>n>>c0>>c1>>vp>>vs; cin>>s>>t; s=" "+s, t=" "+t; for(int i=1;i<=n;i++) sum[i]=sum[i-1]+s[i]-'0';//sum of 1 memset(maxx,-0x3f,sizeof maxx), memset(minn,0x3f,sizeof minn); maxx[0][0]=minn[0][0]=vs*(sum[n]==c1); for(int i=0;i<=n;i++) for(int j=0;j<=n;j++){ int pos=i+j; if(t[pos]!='0'&&j){//? 1 maxx[i][j]=max(maxx[i][j],maxx[i][j-1]+vp*(sum[pos]==j&&pos)+vs*(sum[n]-sum[pos]==c1-j&&pos!=n)); minn[i][j]=min(minn[i][j],minn[i][j-1]+vp*(sum[pos]==j&&pos)+vs*(sum[n]-sum[pos]==c1-j&&pos!=n)); } if(t[pos]!='1'&&i){ maxx[i][j]=max(maxx[i][j],maxx[i-1][j]+vp*(sum[pos]==j&&pos)+vs*(sum[n]-sum[pos]==c1-j&&pos!=n)); minn[i][j]=min(minn[i][j],minn[i-1][j]+vp*(sum[pos]==j&&pos)+vs*(sum[n]-sum[pos]==c1-j&&pos!=n)); } } cout<<minn[c0][c1]<<" "<<maxx[c0][c1]<<endl; return 0; }创作不易,点个赞呗