首页 > 代码库 > 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都被使用
假设我们从高位一直到低位对每个位进行赋值,那么我们会发现根据赋值情况,我们可以根据已经使用的数字(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
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种状态转化而来
第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;
其它同理。
第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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。