首页 > 代码库 > Codeforces 404D [DP]

Codeforces 404D [DP]

/*我是一个习惯后悔,但是没办法忍受内疚感的二货==这题是个无脑dp,但是比赛大概20min没出...其实最后5min我好好想想简单化边界条件,可以出的。题意:给你一个长度为1e6的由?*01四种字符组成的字符串,类似扫雷,?代表当前不确定,0代表当前无雷,并且两边无雷,1代表当前五雷且两边有一个雷,2同样的,问当所有格子已知以后一共有多少种可能的局面。思路:首先想到的是,这个问题无后效性,而当前位置的合法方式只与它之前的两位有关。所以dp的思路也是显而易见的,即dp[i][j]代表前i个最后两位的情况是j的时候的方案数。其实最后两位的一共16种组合合法的方式只有9种。注意:也是我比赛被坑的地方,处理边界条件。首先对于最后的两位是有要求的,例如最后一位不可能是2...(还有其他的情况),答案即把最后两位合法的情况加起来。然后dp一开始的第一位该如何办...我比赛的时候想暴力写前两位的情况,然后dp后来发现这么写代码量...然后崩了....然后刚想了想,其实我枚举第一位所有可能的情况就好。因为合法的9种情况中有许多是等价的,我只需在其中选择一项使得dp[1][i]=1即可 ...然后WA6...因为最后累加答案的时候忘记取模了...傻逼错误简直了==*/#include<bits/stdc++.h>#define N 1000050using namespace std;long long dp[N][10];long long mod=1e9+7;char jilu[N];inline void z(int a,int b,int i){    dp[i][a]+=dp[i-1][b];    dp[i][a]%=mod;}long long ans=0;void ggg(int len){    for(int i=2;i<=len;i++){        if(jilu[i]==?){            z(0,0,i);            z(0,2,i);            z(2,6,i);            z(1,0,i);            z(1,2,i);            z(3,6,i);            z(6,4,i);            z(6,5,i);            z(6,8,i);            z(7,4,i);            z(7,5,i);            z(7,8,i);            z(4,1,i);            z(4,3,i);            z(5,7,i);            z(8,4,i);            z(8,5,i);            z(8,8,i);        }        else if(jilu[i]==0){            z(0,0,i);            z(0,2,i);            z(2,6,i);        }        else if(jilu[i]==1){            z(1,0,i);            z(1,2,i);            z(3,6,i);            z(6,4,i);            z(6,5,i);            z(6,8,i);        }        else if(jilu[i]==2){            z(7,4,i);            z(7,5,i);            z(7,8,i);        }        else{            z(4,1,i);            z(4,3,i);            z(5,7,i);            z(8,4,i);            z(8,5,i);            z(8,8,i);        }    }    ans+=dp[len][0];    ans%=mod;    ans+=dp[len][2];    ans%=mod;    ans+=dp[len][4];    ans%=mod;    ans+=dp[len][5];    ans%=mod;    ans+=dp[len][6];    ans%=mod;    ans+=dp[len][8];    ans%=mod;}int main(){    scanf("%s",jilu+1);    int len=strlen(jilu+1);    if(len<2){        if(jilu[1]==1||jilu[1]==2){            cout << 0 <<endl;        }        else if(jilu[1]==?){            cout << 2 <<endl;        }        else{            cout << 1 <<endl;        }        return 0;    }    switch (jilu[1]){    case ?:        dp[1][0]=1;        dp[1][1]=1;        dp[1][4]=1;        break;    case 0:        dp[1][0]=1;        break;    case 1:        dp[1][1]=1;        break;    case *:        dp[1][4]=1;    }    ggg(len);    cout << ans <<endl;}

 

Codeforces 404D [DP]