题目连接 ： 传送门

题意：

给定一个长度为的二进制串和一个长度为n的序列a[]，我们能够依据这个二进制串得到它的Gray code。

Gray code中假设第i项为1的话那么我们就能够得到a[i]的值，在原来的二进制串中有一些位置为?

表示能够为0，

也能够为1求最后所能得到的最大的值。

已知二进制码怎样得到Gray code请看：传送门

分析：

我们能够通过动态规划来解决问题，状态转移也很好找 ，dp[i][j]表示到第i个位置。第i个位置

取j所能得到的最大值。非常明显这个题的j仅仅能有两种取值0,1.

详细的状态转移看代码。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn = 2e5+10;

typedef long long LL;

char str[maxn];

LL dp[maxn][2];

int a[maxn];

int main()

{

    int n,t,cas=1;

    scanf("%d",&t);

    while(t--){

        scanf("%s",str);

        n=strlen(str);

        for(int i=0;i<n;i++) scanf("%d",a+i);

        memset(dp,0,sizeof(dp));

        if(str[0]=='1'||str[0]=='?

') dp[0][1]= a[0];

        for(int i=1;i<n;i++){

            if(str[i]=='?

'){

                if(str[i-1]=='0')dp[i][1] = dp[i-1][0]+a[i],dp[i][0]=dp[i-1][0];

                if(str[i-1]=='1') dp[i][0] = dp[i-1][1]+a[i],dp[i][1]=dp[i-1][1];

                if(str[i-1]=='?'){

                    dp[i][0] = max(dp[i-1][0],dp[i-1][1]+a[i]);

                    dp[i][1] = max(dp[i-1][1],dp[i-1][0]+a[i]);

                }

            }

            else{

                if(str[i]=='1'&&str[i-1]=='?') dp[i][1] = max(dp[i-1][0]+a[i],dp[i-1][1]);

                if(str[i]=='1'&&str[i-1]=='1') dp[i][1] =dp[i-1][1];

                if(str[i]=='1'&&str[i-1]=='0') dp[i][1] =dp[i-1][0]+a[i];

                if(str[i]=='0'&&str[i-1]=='1') dp[i][0] = dp[i-1][1]+a[i];

                if(str[i]=='0'&&str[i-1]=='?') dp[i][0] = max(dp[i-1][1]+a[i],dp[i-1][0]);

                if(str[i]=='0'&&str[i-1]=='0') dp[i][0] =dp[i-1][0];

            }

        }

        printf("Case #%d: ",cas++);

        if(str[n-1]=='?') printf("%I64d\n",max(dp[n-1][0],dp[n-1][1]));

        if(str[n-1]=='0') printf("%I64d\n",dp[n-1][0]);

        if(str[n-1]=='1') printf("%I64d\n",dp[n-1][1]);

    }

    return 0;

}