题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5375

题意：给你一个二进制串，带’?’的位置可以由你来决定填’1’还是’0’，补充完整之后转换成格雷码表示，每一个位置都有一个权值a[i]，只有格雷码为’1’的位可以加上权值，问你最终权值之和最大为多少。

解法：简单DP。二进制a1 a2 ... an，对应的格雷码为a1 （a1 xor a2） ... （an-1 xor an） 题目就可以转为O(n)的dp dp[i][j]表示二进制第i位为j时前i位对应最大分数.


#include <bits/stdc++.h>
using namespace std;
char str[200010];
int dp[200010][2];
//dp[i][0]表示第i位是0得到的最大值
//dp[i][1]表示第i位是1得到的最大值
int a[200010];
const int inf = 0x3f3f3f3f;
int main()
{
    int T,ks=0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", str);
        int n=strlen(str);
        for(int i=0; i<n; i++) scanf("%d",&a[i]);
        dp[0][1]=dp[0][0]=-inf;
        if(str[0]=='?'||str[0]=='0') dp[0][0]=0;
        if(str[0]=='?'||str[0]=='1') dp[0][1]=a[0];
        for(int i=1; i<n; i++){
            dp[i][0]=dp[i][1]=-inf;
            if(str[i]=='0'||str[i]=='?')
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
            if(str[i]=='1'||str[i]=='?')
                dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i]);
        }
        printf("Case #%d: %d\n", ++ks, max(dp[n-1][0],dp[n-1][1]));
    }
    return 0;
}