HDU 5375 Gray code（DP）

题意：给一串字符串，里面可能出现0,1,?，当中问号可能为0或1，将这个二进制转换为格雷码后，格雷码的每位有一个权值，当格雷码位取1时。加上该位权值，求最大权值和为多少。

分析：比赛的时候愚了。竟然以为格雷码是由3个二进制字符转换的，于是妥妥wa了，事实上格雷码的求法是通过异或求的的，即Gi=Bi⊕Bi-1（G为格雷码，B为二进制数），那么仅仅要水水的DP一下就好了。详细DP是通过保存

DP[i][j]，当中i为当前位。j表示当前为为0还是1，递推式为：

一、s[i]为0时

1.s[i-1]为0，dp[i][0]=dp[i-1][0];

2.s[i-1]为1，dp[i][0]=dp[i-1][1]+v[i];

3.s[i-1]为？,dp[i][0]=max(dp[i-1][0],dp[i-1][1]+v[i]);

二、s[i]为1时

1.s[i-1]为0，dp[i][1]=dp[i-1][0]+v[i];

2.s[i-1]为1。dp[i][1]=dp[i-1][1];

3.s[i-1]为？,dp[i][1]=max(dp[i-1][0]+v[i],dp[i-1][1]);

三、s[i]为？时，就是结合上面两种情况

1.s[i-1]为0，dp[i][0]=dp[i-1][0],dp[i][1]=dp[i-1][0]+v[i];

2.s[i-1]为1，dp[i][0]=dp[i-1][1]+v[i],dp[i][1]=dp[i-1][1];

3.s[i-1]为？,dp[i][0]=max(dp[i-1][0],dp[i-1][1]+v[i]),dp[i][1]=max(dp[i-1][0]+v[i],dp[i-1][1]);

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include<vector>
#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int maxn = 2e5+5;
char s[maxn];
int v[maxn];
int dp[maxn][3];
int main()
{
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        memset(dp,0,sizeof(dp));
        scanf("%s",s+1);
        int n=strlen(s+1);
        s[0]='0';
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='1') {
                if(s[i-1]=='?')
                dp[i][1]=max(dp[i-1][0]+v[i],dp[i-1][1]);
                else if(s[i-1]=='0') dp[i][1]=dp[i-1][0]+v[i];
                else dp[i][1]=dp[i-1][1];
            }
            if(s[i]=='0') {
                if(s[i-1]=='?')
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]+v[i]);
                else if(s[i-1]=='0') dp[i][0]=dp[i-1][0];
                else dp[i][0]=dp[i-1][1]+v[i];
            }
            if(s[i]=='?
'){
                if(s[i-1]=='?'){
                    dp[i][1]=max(dp[i-1][0]+v[i],dp[i-1][1]);
                    dp[i][0]=max(dp[i-1][0],dp[i-1][1]+v[i]);
                }
                else if(s[i-1]=='0'){
                    dp[i][1]=dp[i-1][0]+v[i];
                    dp[i][0]=dp[i-1][0];
                }
                else{
                    dp[i][1]=dp[i-1][1];
                    dp[i][0]=dp[i-1][1]+v[i];
                }
            }
        }
        printf("Case #%d: %d
",cas,max(dp[n][0],dp[n][1]));
    }
}