hdu 5375 Gray code(dp)

제목:

2진 코드를 주십시오. 그 중 일부 위치는 물음표가 있습니다. 물음표에 0 또는 1로 변환된 그레이코드의 i번째 위치가 1이면 a[i]의 권한을 얻을 수 있습니다.최대 얼마의 권한을 얻을 수 있느냐고 묻다

해결:

2진 코드에서 그레코드로 전환하는 공식은 2진 코드를 오른쪽으로 한 자리 옮긴 다음에 원래의 2진 코드와 위치가 다르거나 다르다는 것이다.그래서 dp수 그룹 dp[i][0]를 열면 i위는 0이 얻은 최대치 dp[i]를 나타낸다[1]. i위는 1이 얻은 최대치라고 한다. 그러면 0은 1oxr1 또는 0xor0이 옮길 수 있기 때문에 dp[i][0]=max(dp[i - 1][0], dp[i - 1][1]+a[i]))
그러면 1은 1oxr0 또는 0xor0으로만 옮길 수 있기 때문에 dp[i][1]=max(dp[i-3-1][1], dp[i-3-1][0]+a[i])
my code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 200005;
char bit[MAXN];
int A[MAXN], dp[MAXN][2];
int main() {
    int T, cas = 1;
    scanf("%d", &T);
    while(T--) {
        scanf("%s", bit+1);
        int len = strlen(bit+1);
        for(int i = 1; i <= len; i++) {
            scanf("%d", &A[i]);
        }
        dp[0][0] = 0;
        dp[0][1] = -INF;
        for(int i = 1; i <= len; i++) {
            if(bit[i] == '1') {
                dp[i][1] = max(dp[i-1][0] + A[i], dp[i-1][1]);
                dp[i][0] = -INF;
            }else if(bit[i] == '0') {
                dp[i][0] = max(dp[i-1][1] + A[i], dp[i-1][0]);
                dp[i][1] = -INF;
            }else if(bit[i] == '?') {
                dp[i][1] = max(dp[i-1][0] + A[i], dp[i-1][1]);
                dp[i][0] = max(dp[i-1][1] + A[i], dp[i-1][0]);
            }
        }
        printf("Case #%d: %d
", cas++, max(dp[len][0], dp[len][1]));
    }
    return 0;
}