首页 > 代码库 > CCF_有趣的数
CCF_有趣的数
题目链接:
http://115.28.138.223:81/view.page?opid=4
思路:
dp题,dp[i][j]代表i位数,j状态的数量。
其中,j 的状态表示值有6种。
0
1
2 √ j = 0
3
01
02 √ j = 1
03
12
13
23 √ j = 2
012 √ j = 3
013
023 √ j = 4
123
0123 √ j = 5
其中,i位数各状态的数量由i-1位数各状态的数量推出。
#include<cstdio>#include<iostream>using namespace std;#define MOD 1000000007long long dp[1005][6];//2 0 1//02 1 3//23 2 2//012 3 1//023 4 2//0123 5 0int main(){ dp[3][0] = 1; dp[3][1] = 3; dp[3][2] = 2; dp[3][3] = 1; dp[3][4] = 2; dp[3][5] = 0; int n; cin >> n; for(int i = 4;i <= n;i++) { dp[i][0] = 1; dp[i][1] = (dp[i-1][0]+dp[i-1][1]*2)%MOD; dp[i][2] = (dp[i-1][0]+dp[i-1][2])%MOD; dp[i][3] = (dp[i-1][1]+dp[i-1][3]*2)%MOD; dp[i][4] = (dp[i-1][1]+dp[i-1][2]+dp[i-1][4]*2)%MOD; dp[i][5] = (dp[i-1][3]+dp[i-1][4]+dp[i-1][5]*2)%MOD; } cout << dp[n][5] << endl; return 0;}
CCF_有趣的数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。