BestCoder Round #75 King’s Order dp：数位dp

Source

The question is from BC and hduoj 5642.

My Solution

数位dp

状态： d[i][j][k] 为处理完i 个字符 , 结尾字符为′a′+j , 结尾部分已重复出现了 k 次的方案数;

边界：d[1][j][1] = 1; (1 <= j <= 26 );

状态转移方程：看代码吧;

#include 
#include 
#include 
using namespace std;
const int maxn = 2000+6;
const int HASH = 1000000007;
long long d[maxn][27][4];
int main()
{
    int T, n;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        memset(d, 0, sizeof(d));
        for(int j = 1; j <= 26; j++){
            d[1][j][1] = 1; //d[0][j][2] = 0; d[0][j][3] = 0;//they are not needed.
            //d[1][j][2] = 1;                           these two are wrong and not needed.
            //d[2][j][3] = 1;                           these two are wrong and not needed.
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= 26; j++){
                d[i][j][2] = (d[i][j][2]+d[i-1][j][1])%HASH;          // 2
                d[i][j][3] = (d[i][j][3]+d[i-1][j][2])%HASH;          // 3
                for(int k = 1; k <= 26; k++){
                    if(j != k) d[i][j][1] = ( ( (d[i][j][1]+d[i-1][k][1])%HASH + d[i-1][k][2])%HASH + d[i-1][k][3])%HASH;
                }
            }
        }
        long long ans = 0;
        for(int j = 1; j <= 26; j++){
                for(int k = 1; k <= 3; k++ ){
                   ans = (ans + d[n][j][k]) %HASH;
                }
        }
        cout<<ans<<endl;
        //printf("%lldn", ans);  this website : %I64d
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx