首页 > 代码库 > 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_有趣的数