给你一个二进制数，，每一位有一个权值，让你转格雷码，求所对应格雷码位为1的权值的和；二进制位中的某些位为?，你需要给这些问号赋值使得到的和最大。
首先你得知道二进制转格雷码的规则，即格雷码位为【二进制位与左边前一位的异或值】，格雷码首位为二进制首位；
因为格雷码首位为二进制首位，那么可以视二进制首位的左边前一位是0；
然后你就可以分情况模拟了：
1、连续数字的情况直接计算即可；
2、连续问号的情况需要dp一下：dp[k][j]表示第k个问号是j时，得到的最大和，那么dp[k][j] = max(dp[k-1][!j]+w[i], dp[k-1][j]);首尾的细节处要处理好；
这里也可以不用dp直接模拟求，需要分一下问号数的奇偶性，比较复杂不再讨论了；
附代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = ;
char bin[maxn];
int w[maxn];
int dp[maxn][]; int main()
{
int T;
scanf("%d", &T);
for(int kase = ; kase <= T; kase++)
{
scanf("%s", bin+);
bin[] = '';
int len = strlen(bin+);
for(int i = ; i<= len; i++)
scanf("%d", &w[i]); int ans = , i = len;
while(i >= )
{
if(bin[i] != '?')
{
if(bin[i-] == '?') // X????1 连问号且尾接数字，dp[i][j]为（从右向左问号的）第i位为j时最大值：dp[i][j] = (dp[i][!j]+w[i] , dp[i][j]);
{
int pos = ; //注意结尾的数字要单独考虑，结尾(bin[i])是1，则dp[1][0]=w[i]，dp[1][1]=0；是0，则dp[1][1]=w[i]，dp[1][0]=0
dp[pos][] = w[i]*((bin[i]-'')^);
dp[pos][] = w[i]*((bin[i]-'')^);
pos++; i--; //i指向当前考虑的格雷码位，pos指向i的前一位对应的从右向左的第几个'?'
while(i && bin[i-] == '?')
{
dp[pos][] = max(dp[pos-][] + w[i], dp[pos-][]);
dp[pos][] = max(dp[pos-][] + w[i], dp[pos-][]);
pos++; i--;
}
//前面的数字也要单独考虑，若bin[i-1]是1，则max_val=max(dp[pos-1][0] + w[i], dp[pos-1][1]);
dp[pos][bin[i-] - ''] = max(dp[pos-][!(bin[i-] - '')] + w[i], dp[pos-][bin[i-] - '']);
ans += dp[pos][bin[i-] - ''];
i--;
}
else // X11111 连数字，直接与前一位异或计算即可
{
while(i && bin[i-] != '?')
{
ans += ((bin[i]-'')^(bin[i-]-'')) * w[i];
i--;
}
}
}
else // X???? 连问号且尾不接数字，可以保证其格雷码'?'处全为1
{
while(i && bin[i] == '?')
{
ans += w[i];
i--;
}
}
}
printf("Case #%d: %d\n", kase, ans);
}
return ;
}
hdu 5375
最近易激动，大约是亲戚来的缘故吧。有点想家了。
加油吧，在这个优胜劣汰的游戏中，努力生存下去吧。