- 有趣的數
題目
提交記錄
討論
題解
視頻講解
我們把一個數稱為有趣的，當且僅當：
它的數字只包含 0,1,2,3，且這四個數字都出現過至少一次，
所有的 0 都出現在所有的 1 之前，而所有的 2 都出現在所有的 3 之前，
最高位數字不為 0，
因此，符合我們定義的最小的有趣的數是 2013，
除此以外，4 位的有趣的數還有兩個：2031 和 2301，
請計算恰好有 n 位的有趣的數的個數，
由于答案可能非常大，只需要輸出答案除以 109+7 的余數，
輸入格式
輸入只有一行，包括恰好一個正整數 n，
輸出格式
輸出只有一行，包括恰好 n 位的整數中有趣的數的個數除以 109+7 的余數，
資料范圍
4≤n≤1000
輸入樣例：
4
輸出樣例：
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－－全部用了
于是我們需要讓用戶輸入位數，然后宣告同等位數的陣列，在每個元素里是6種狀態中所包含的該狀態下的“符合條件的數”的個數，（是二維陣列）
然后用動態規劃思想從最小位數開始逐層往上計算，
例：
對于i位狀態5的計算，考慮在i－1位時有三種狀態可以到達狀態5，第3種，此時只能在i位填3，所以＊1；第4種，此時只能在i位填1，所以＊1；第5種，此時能在i位填2或3（參考規則），所以＊2；
states[i][5] = (states[j][3] + states[j][4] + states[j][5] * 2) % mod;
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6;
const int p=1e9+7;
int a[maxn];
int n;
ll dp[maxn][6];
int main()
{
/*6種狀態
* 0－－剩013//用了2
* 1－－剩13 //用了0,2
* 2－－剩01 //用了2,3
* 3－－剩3 //用了0,1,2
* 4－－剩1 //用了0,2,3,
* 5－－無 //全用了
*/
ll n;
cin>>n;
for(ll i=1;i<=n;i++)
{
dp[i][0]=1;
dp[i][1]=(dp[i-1][1]*2%p+dp[i-1][0])%p;
dp[i][2]=(dp[i-1][2]+dp[i-1][0])%p;
dp[i][3]=(dp[i-1][1]+dp[i-1][3]*2)%p;
dp[i][4]=(dp[i-1][2]+dp[i-1][1]+dp[i-1][4]*2)%p;
dp[i][5]=(dp[i-1][3]+dp[i-1][4]+dp[i-1][5]*2)%p;
}
cout<<dp[n][5]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260669.html
標籤：其他
上一篇：使用云開發每天定時向女朋友發送短信(api獲取/資料庫固定+情話用完短信警告/自定義情話/晚安)
下一篇：【二、飛機游戲 (1)】