Sample Input
2
00?0
1 2 4 8
????
1 2 4 8
00?0
1 2 4 8
????
1 2 4 8
Sample Output
Case #1: 12
Case #2: 15
Case #2: 15
？部分可以是0 or 1，将二进制转化成格雷码后，哪里是 1 就可以取相应的数，求得到数的最大值
①：判断连续的？的个数奇偶不同，两边是否相等。在有时会去掉一个最小值。（感觉写着很麻烦）
#include <iostream>
#include <cstdio>
#include <vector>
#include<cstring>
using namespace std;
char s[200010];
int a[200010];
int main()
{
int k=1;
int case0;
scanf("%d",&case0);
while(case0--)
{
scanf("%s",s);
int leng=strlen(s);
int i,j;
for(i=0; i<leng; i++)
scanf("%d",&a[i]);
long long int ssum,sum;
ssum=0; for(i=0;i<leng; i++)
{
if(s[i]=='?')
{
sum=0;
int min1=0x3f3f3f3f;
for(j=i; s[j]=='?'; j++)
{
sum+=a[j];
if(min1>a[j])
min1=a[j];
}
if(s[j]!='\0')
{
sum+=a[j];
if(min1>a[j])
min1=a[j];
}
if(i==0&&((s[j]=='1'&&(j-i)%2==1)||(s[j]=='0'&&(j-i)%2==0)))
sum-=min1;
if(i!=0&&s[j]!='\0')
{
if(s[i-1]==s[j]&&(j-i)%2==0)
sum-=min1;
if(s[i-1]!=s[j]&&(j-i)%2==1)
sum-=min1;
}
ssum+=sum;
i=j; }
else if(i==0&&s[i]=='1')
ssum+=a[i];
else if(s[i]!=s[i-1]&&i!=0)
ssum+=a[i];
}
printf("Case #%d: ",k++);
cout<<ssum<<endl;
}
return 0;
}
②dp
dp[i][0]表示第i个位置上取0.
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+a[i]);
既然能够得到 i 与 i - 1 的关系，自然推出。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 100010
using namespace std;
const int INF = 0x3f3f3f3f;
char s[200050];
int a[200050];
int dp[200050][2];
int main()
{
int T;
int cas = 1;
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
int len = strlen(s);
for(int i = 0; i < len; i++)
scanf("%d",&a[i]);
dp[0][0] = dp[0][1] = -INF; if(s[0] == '0' || s[0] == '?')
dp[0][0] = 0;
if(s[0] == '1' || s[0] == '?')
dp[0][1] = a[0]; for(int i = 1;i < len;i++)
{
dp[i][0] = dp[i][1] = -INF;
if(s[i] == '0' || s[i] == '?')
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+a[i]);
if(s[i] == '1' || s[i] == '?')
dp[i][1] = max(dp[i-1][0]+a[i],dp[i-1][1]);
} printf("Case #%d: %d\n",cas++,max(dp[len-1][0],dp[len-1][1]));
}
return 0;
}