CCF认证——有趣的数（数位DP）

题目：

问题描述　　我们把一个数称为有趣的，当且仅当：
　　1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
　　2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
　　3. 最高位数字不为0。
　　因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。输入格式　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。输出格式　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。样例输入 4 样例输出 3题目来源： CCF--有趣的数

思路：

在浏览了很多大神的题解后终于明白了。

数位DP;

在本题中首先定义状态dp[i][j]，记为长度为i的数字串中，状态为j的情况个数

本题中可以分析出6中状态：

0. 在前n位数中只有一种数字且为2
1. 在前n位数中有两种数字为 2,0
2. 在前n为数中有两种数字为 2,3
3. 在前n位数中有三种数字为 2,0,1
4. 在前n位数中有三种数字为 2,0,3
5. 在前n位数中有四种数字为 2,0,1,3

然后就是状态转移方程：

对于每种状态dp[i][j]，其可由长度为i-1的数字串在后面加上一种数字得到

即dp[i][j] = ∑(dp[i-1][可以通过加上某种数字得到第j种状态的状态]);

复杂度：

时间复杂度：O(N)

空间复杂度：O(N)

CCF认证——有趣的数（数位DP）

#include<iostream>
#include<cstring>
#define MAX 1007
using namespace std;
typedef long long ll; 
const ll mod=1000000007;

ll dp[MAX][6]; //  dp[i][j]表示i位数为第j种状态的种数 

int main(){
    int n;
    cin>>n;

    /*
    数位DP
      本题共有6中状态
      0. 在前n位数中只有一种数字且为2
  1. 在前n位数中有两种数字为 2,0
  2. 在前n为数中有两种数字为 2,3
  3. 在前n位数中有三种数字为 2,0,1
  4. 在前n位数中有三种数字为 2,0,3
  5. 在前n位数中有四种数字为 2,0,1,3 
    */

    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;++i){
    //第0种状态，由于只有2，所以始终只有一种情况 
    dp[i][0] = 1;
//第1种状态，由于为2,0，可以在dp[i-1][1]后加0或2，或者在dp[i-1][0]后面加上0  
    dp[i][1] = (dp[i-1][1]*2 + dp[i-1][0])%mod;
    //第2种状态，由于为2,3，可以在dp[i-1][1]后加3(不能加2,2必须在3前),或者在dp[i-1][0]后加3 
    dp[i][2] = (dp[i-1][2] + dp[i-1][0])%mod;
    //第3种状态，由于为2,0,1，可以在dp[i-1][3]后加2,1(不能加0,0必须在1前),或者在dp[i-1][1]后加1 
    dp[i][3] = (dp[i-1][3]*2 + dp[i-1][1])%mod;
    //第4种状态，由于为2,0,3，可以在dp[i-1][4]后加0,3，或者在dp[i-1][1]后加3，或者在dp[i-1][2]后加0 
    dp[i][4] = (dp[i-1][4]*2 + dp[i-1][1] + dp[i-1][2])%mod;
    //第5种状态，由于为2,0,1,3,可以在dp[i-1][5]后加1,3，或者在dp[i-1][3]后加3，或者在dp[i-1][4]后加1 
    dp[i][5] = (dp[i-1][5]*2 + dp[i-1][3] + dp[i-1][4])%mod;
    }

cout<<dp[n][5]<<endl; 
return 0;
}

秒客网

CCF认证——有趣的数（数位DP）

相关文章