首页 > 代码库 > CCF-有趣的数(数位DP)

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
 
原理:动态规划
假设我们从高位一直到低位对每个位进行赋值,那么我们会发现根据赋值情况,我们可以根据已经使用的数字(0,1,2,3)将数据分为6种状态:
1、首先我们从最高位开始,由于0,2分别需在1,3前面而0又不能放置在最高位,最高位只能是2,因此我们得到第一种状态,即前n-1位都是为2的情况。
2、现在我们再放置一个数,目前有0,1,3没用,由于0必须在1前面,所以我们在放置1是必须先放置0。此时我们可以放置0或者3,基于此,我们得到两种状态,一种是前n-1为只有2、0;另一种前n-1位只有2、3。
3、现在我们再放置一个数,对于已经放置2和0的状态,我们可以放置1或3,则又得到两种状态,分别是2、0、1和2、0、3;对于已经放置2和3的状态,我们只能放置0(0必须优先放于1前面)。得到状态2、3、0(此状态和2、0、3相同)
4、最后一种所有0,1,2,3都被使用
 
6重状态如下:
   0--用了2,剩0,1,3
  1--用了0,2,剩1,3
  2--用了2,3,剩0,1
  3--用了0,1,2,剩3
  4--用了0,2,3,剩1
  5--0,1,2,3
后面的状态由前面状态转化而来。如:
第5种状态全部使用可以由第5中状态自身维持或第3种状态或第4种状态转化而来
转化如下:假设从n-1到n位
第5中状态自身维持:可以在n位放置1或3(维持自身状态不变只能放置1或3,因为前面已经有1,3所以再放0,2就会违反规则)
第3种状态:可以在n位放置3
第4种状态:可以在n位放置1
得到如下公式:
states[i][5] = (states[j][3](达到状态五仅有在1后加3) + states[j][4] ](达到状态五仅有2301)+ states[j][5] * 2(达到状态五仅有加1/3) % mod;
其它同理。
 
代码如下:
 1 #include <iostream>
 2   
 3   using namespace std;
 4   
 5   int main(){
 6       long long mod = 1000000007;
 7       long long n;
 8       cin>>n;
 9       long long **states = new long long*[n+1];
10     for(long long i =0;i<n+1;i++)
11          states[i]=new long long[6];
12      for(long long i =0;i<6;i++)
13         states[0][i]=0;
14      /*6种状态
15      * 0--剩013
16     * 1--剩13
17     * 12-剩01 
18      * 3--剩3
19      * 4--剩1
20       * 5--无
21      */
22      for(long long i=1;i<=n;i++)
23      {
24          long long j = i-1;
25         states[i][0] = 1;
26         states[i][1] = (states[j][0] + states[j][1] * 2) % mod;
27          states[i][2] = (states[j][0] + states[j][2]) % mod;
28          states[i][3] = (states[j][1] + states[j][3] * 2) % mod;
29          states[i][4] = (states[j][1] + states[j][2] + states[j][4] * 2) % mod;
30         states[i][5] = (states[j][3] + states[j][4] + states[j][5] * 2) % mod;
31     }
32      cout<<states[n][5]<<endl;
33      return 0;
34  }

 

CCF-有趣的数(数位DP)