MYF

HDU 5375Gray code

Posted on | In | | Visitors

题目链接

HDU 5375

解题方法：动态规划

题目分析

题目大意

给出了格雷码的定义：

格雷码的最高位与原数字的最高位相同，从第二位到最后一位为：当前位的值抑或前一位的值。

比如，原数字为1100则格雷码的第一位和原数字的第一位相同，为1，第二位为原数字的前两个数的抑或即1^1=0，第三位为原数字的第二个和第三个位的抑或即1^0=0，第四位为原数字的第三个和第四个位的抑或即0^0=0。

给出了每一位的价值，问这个数字能形成的的最大价值是多少

解析

按位进行状态转移

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
char a[200005]={};
int w[200005]={};
int dp[200005][3]={};
int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while (t--) {
        
        int n;
        scanf("%s",a+1);
        n=strlen(a+1);
        for (int i=1; i<=n; i++) {
            scanf("%d",&w[i]);
        }
        dp[0][1]=-INF;
        for (int i=1; i<=n; i++) {
            if (a[i]=='0') {
                dp[i][1]=-INF;
                dp[i][0]=max(dp[i-1][0], dp[i-1][1]+w[i]);
            }
            else if (a[i]=='1'){
                dp[i][0]=-INF;
                dp[i][1]=max(dp[i-1][1], dp[i-1][0]+w[i]);
            }
            else{
                dp[i][0]=max(dp[i-1][0], dp[i-1][1]+w[i]);
                dp[i][1]=max(dp[i-1][1], dp[i-1][0]+w[i]);
            }
        }
        printf("Case #%d: ",++cas);
        cout<<max(dp[n][0], dp[n][1])<<endl;
    }
    return 0;
}