hdu 5375 dp

1430 단어
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0X3f3f3f;
const int MAXN = 2e5+10;
char str[MAXN];
int a[MAXN];
int dp[MAXN][2];

int main(){
    int t;
    int mycase=0;
    int n;
    //int k=INF;
    //cout<<k;
    cin>>t;
    while(t--){
        scanf("%s",str);
        n = strlen(str);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        dp[0][1] = dp[0][0] = -INF;
        if(str[0]=='1'||str[0]=='?')
            dp[0][1] = a[0];
        if(str[0]=='0'||str[0]=='?')
            dp[0][0] = 0;
        for(int i=1;i<n;i++){
            dp[i][1] = -INF;
            dp[i][0] = -INF;
            if(str[i]=='1'||str[i]=='?')
                dp[i][1] = max(dp[i-1][1],dp[i-1][0]+a[i]);
            if(str[i]=='0'||str[i]=='?')
                dp[i][0] = max(dp[i-1][0],dp[i-1][1]+a[i]);
        }
        cout<<"Case #"<<++mycase<<":"<<" "<<max(dp[n-1][0],dp[n-1][1])<<endl;
    }
}

좋은 웹페이지 즐겨찾기