2015-10-05

http://acm.hdu.edu.cn/showproblem.php?pid=5375

 

DP

 

#include
     
      #define N 200010using namespace std;int f[N][2],a[N];char s[N];int main(){    int T,n,ans,Case=0;    scanf("%d",&T);    while(T--)    {        //scanf("%d",&n);        scanf("%s",s);        n=strlen(s);        for (int i=0;i
      
       0)                {                    if (s[i-1]!='?')                    {                        if (s[i-1]!=s[i]) ans+=a[i];                    }                    else                    {                        if (s[i]=='0') ans+=max(f[i-1][1]+a[i],f[i-1][0]);                        if (s[i]=='1') ans+=max(f[i-1][0]+a[i],f[i-1][1]);                    }                }                else                {                    if (s[i]=='0') ans=0;                    if (s[i]=='1') ans=a[i];                }            }            else            {                if (i>0)                {                    if (s[i-1]!='?')                    {                        if (s[i-1]=='0') f[i][0]=0,f[i][1]=a[i];                        if (s[i-1]=='1') f[i][0]=a[i],f[i][1]=0;                    }                    else                    {                        f[i][0]=max(f[i-1][0],f[i-1][1]+a[i]);                        f[i][1]=max(f[i-1][0]+a[i],f[i-1][1]);                    }                }                else                {                    f[i][0]=0;                    f[i][1]=a[i];                }            }        }        if (s[n-1]=='?') ans=ans+max(f[n-1][0],f[n-1][1]);        printf("Case #%d: %d\n",++Case,ans);    }    return 0;}