Gray code
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 569 Accepted Submission(s): 337
Now , you are given a binary number of length n including ‘0’ , ’1’ and ‘?’(? means that you can use either 0 or 1 to fill this position) and n integers(a1,a2,….,an) . A certain binary number corresponds to a gray code only. If the ith bit of this gray code is 1,you can get the point ai.
Can you tell me how many points you can get at most?
For instance, the binary number “00?0” may be “0000” or “0010”,and the corresponding gray code are “0000” or “0011”.You can choose “0000” getting nothing or “0011” getting the point a3 and a4.
Each test case begins with string with ‘0’,’1’ and ‘?’.
The next line contains n (1<=n<=200000) integers (n is the length of the string).
a1 a2 a3 … an (1<=ai<=1000)
https://en.wikipedia.org/wiki/Gray_code
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=1e5+200;
const int INF=0x3f3f3f3f;
int dp[2*maxn][2];
int a[2*maxn];
char str[2*maxn];
int main(){
int t,cnt=0;
scanf("%d",&t);
while(t--){
scanf("%s",str+1);
int len=strlen(str+1);
for(int i=1;i<=len;i++){
scanf("%d",&a[i]);
dp[i][1]=dp[i][0]=-INF;
}
if(str[1]=='0'){
dp[1][0]=0;
}else if(str[1]=='1'){
dp[1][1]=a[1];
}else{
dp[1][0]=0;
dp[1][1]=a[1];
}
for(int i=2;i<=len;i++){
if(str[i]=='0'){
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
}else if(str[i]=='1'){
dp[i][1]=max(dp[i-1][0]+a[i],dp[i-1][1]);
}else {
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\n",++cnt,max(dp[len][1],dp[len][0]));
}
return 0;
}
讨论：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e6+200;
const int INF=0x3f3f3f3f;
char str[2*maxn];
int a[maxn*2];
int main(){
int t,cnt=0;
scanf("%d",&t);
while(t--){
scanf("%s",str);
int len=strlen(str);
for(int i=0;i<len;i++)
scanf("%d",&a[i]);
int sum=0,pos=len,flag=-1;
int i;
for(i=len-1;i>=0;i--){ //逆序处理
if(str[i]=='0'){
if(flag==1){ //如果右边有1
sum+=a[pos];
}
flag=0; //表示当前是0
pos=i;
continue;
}else if(str[i]=='1'){
if(flag==0){
sum+=a[pos];
}
flag=1;
pos=i;
continue;
}else{ //是问号
int num=0,sumv,minv;
if(flag!=-1){
minv=a[pos],sumv=a[pos];
}
else {
minv=INF,sumv=0;
}
int j;
for(j=i;j>=0;j--){
if(str[j]=='0'){
if(flag==1){
if(num%2==1){ //如果问号两边不同，且中间的问号为奇数个，舍弃这段中的最小值
sum+=(sumv-minv);
}else {
sum+=sumv;
}
}else if(flag==0){
if(num%2==1){ //如果两边相同，且中间为奇数个，加上这段所有值
sum+=sumv;
}else{
sum+=(sumv-minv);
} }else{
sum+=sumv;
}
flag=-1;
pos=len;
i=j+1;
break;
}else if(str[j]=='1'){
if(flag==0){
if(num%2==1){
sum+=(sumv-minv);
}else{
sum+=sumv;
}
}else if(flag==1){
if(num%2==0){
sum+=(sumv-minv);
}else{
sum+=sumv;
}
}else{
sum+=sumv;
}
flag=-1;
pos=len;
i=j+1;
break;
}else {
num++;
sumv+=a[j];
if(minv>a[j]){
minv=a[j];
}
}
}
if(j==-1){ //边界处理，比较恶心
i=0;
if(flag==-1 )
sum+=sumv;
else if (flag==1){
if(num%2==0){
sum+= sumv;
}
else sum+=(sumv-minv);
}else {
if(num%2==1){
sum+=sumv;
}else{
sum+=(sumv-minv);
}
}
}
}
}
if(str[0]=='1'&&i==-1){ //字串第一位
sum+=a[0];
}
printf("Case #%d: %d\n",++cnt,sum);
}
return 0;
}