CCF201312-4 -有趣的数（数位DP or 神奇思路)

￡神魔★判官ぃ 2022-05-17 11:57 123阅读 0赞

题目链接：  
[有趣的数][Link 1]

解题思路：  
好吧，一点都没趣，看了题目拼命想着组合数学！！！  
一晚上无果，，，  
决定看一下各路神仙的做法，真是人才啊！服

解题的关键是把可能存在的状态找出来！  
可以这样分析：由题容易知道，肯定肯定以2开头，然后无0，肯定无1，。所以可以得出以下6中状态：  
dp\[i\]\[0\] :前i为数中只有2  
dp\[i\]\[1\]:前i位数中只有0 2  
dp\[i\]\[2\]:前i位数中只有2 3  
dp\[i\]\[3\]:前i位数中只有0 1 2  
dp\[i\]\[4\]:前i位数中只有0 2 3  
dp\[i\]\[5\]:前i位数有0 1 2 3

那么直接不断更新(具体看代码，有详细解释）就好了  
对了，需要提醒各位，更新过程中可能\*2会导致int类型超出  
所以我们dp需要声明为long long

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    long long dp[1005][6];
    const long long MOD = 1000000007;
    
    int main(){
        int n;
        scanf("%d",&n);
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; ++i){
            dp[i][0] = 1;
            //只有2那只有一种情况
            dp[i][1] = (dp[i-1][0] + dp[i-1][1]*2)%MOD; 
            //只有2的情况和只有0 2的情况，可以添加0或2，所以*2 
            dp[i][2] = (dp[i-1][0] + dp[i-1][2])%MOD; 
            //只有2的情况和只有2，3的情况，但是只能添加3，所以直接加上前一个就好 
            dp[i][3] = (dp[i-1][1] + dp[i-1][3]*2)%MOD;
            //只有0 2的情况（这里不用加上只有2的情况，加上的话会重复计算）+只有0 1 2但是只能添加0 2的情况
            dp[i][4] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][4]*2)%MOD;
            // 只有0 2的情况+只有2 3情况（只能添加3）+只有0 2 3的情况（只能添加0 3）
            dp[i][5] = (dp[i-1][3] + dp[i-1][4] + dp[i-1][5]*2)%MOD;
            //同上解释了，自己琢磨23333 
        }
        printf("%lld\n",dp[n][5]);
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T2