HDU 5375 Gray Code 动归

题意：给你一串不确定的二进制码，其对应的格雷码的每一位有对应的权值，问转换成的格雷码的能取到的最大权值是多少。

思路：没有思路，乱搞也AC

 1 #pragma comment(linker, "/STACK:1000000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <deque>
 8 #include <vector>
 9 #include <queue>
10 #include <string>
11 #include <cstring>
12 #include <map>
13 #include <stack>
14 #include <set>
15 #define LL long long
16 #define MAXN 100005
17 #define INF 0x3f3f3f3f
18 #define eps 1e-8
19 using namespace std;
20 char s[200005];
21 LL a[200005];
22 LL f[200005][3];
23 int main()
24 {
25 #ifndef ONLINE_JUDGE
26     freopen("in.txt", "r", stdin);
27     //freopen("out.txt", "w", stdout);
28 #endif // OPEN_FILE
29     int T;
30     scanf("%d", &T);
31     int cas = 1;
32     while(T--){
33         scanf("%s", s + 1);
34 
35         int m = strlen(s + 1);
36         for(int i = 1; i <= m; i++){
37             scanf("%I64d", &a[i]);
38         }
39         LL ans = 0;
40         int last;
41         memset(f, -1, sizeof(f));
42         if(s[1] != '0'){
43             f[1][1] = a[1];
44         }
45         if(s[1] != '1'){
46             f[1][0] = 0;
47         }
48         for(int i = 2; i <= m; i++){
49             if(s[i] == '0' || s[i] == '?'){
50                 if(f[i - 1][1] >= 0){
51                     f[i][0] = max(f[i][0], f[i - 1][1] + a[i]);
52                 }
53                 if(f[i - 1][0] >= 0){
54                     f[i][0] = max(f[i][0], f[i - 1][0]);
55                 }
56             }
57             if(s[i] == '1' || s[i] == '?'){
58                 if(f[i - 1][0] >= 0){
59                     f[i][1] = max(f[i][1], f[i - 1][0] + a[i]);
60                 }
61                 if(f[i - 1][1] >= 0){
62                     f[i][1] = max(f[i][1], f[i - 1][1]);
63                 }
64             }
65         }
66         printf("Case #%d: %I64d
", cas++, max(f[m][1], f[m][0]));
67     }
68 }