#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200008; char s[maxn]; int dp[maxn][2],a[maxn]; int main() { int i,j,k; int t,n; int cas=1; scanf("%d",&t); while(t--) { scanf("%s",s+1); n=strlen(s+1); s[0]=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); dp[i][0]=dp[i][1]=-1e9; } dp[0][0]=0;dp[0][1]=-1e9; //printf("%d %d ",dp[0][1],1000*200000); for(i=1;i<=n;i++) { if(s[i]=='?') { dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]); dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]); } else if(s[i]=='1') { dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]); } else if(s[i]=='0') { dp[i][0]=max(dp[i-1][1]+a[i],dp[i-1][0]); } } printf("Case #%d: %d ",cas++,max(dp[n][1],dp[n][0])); } return 0; }
多校水dp,分类讨论即可