円円送禮物
題目連結
以後寫DP幾種組合問題就是像這一題一樣暴力破解
把每一種情況都寫清楚，不惜開三維陣列也沒關係
總之，$dp[i][k][j]$ 代表長度為i，左邊為顏色k，右邊為顏色j
（紅色：0、綠色：1、藍色：2）
列出每一種狀態的轉移式就好
不過，即使頭尾是一藍一綠，但也必須轉移，因為一藍一綠可以在頭或尾加上其他顏色，組成合法解，不過不要輸出就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
int t;
signed main(){
ios;
int dp[100005][3][3];
dp[1][0][0] = 1;dp[1][1][1] = 1;dp[1][2][2] = 1;
dp[2][0][0] = dp[2][0][1] = dp[2][0][2] = 1;
dp[2][1][0] = dp[2][1][1] = dp[2][2][0] = dp[2][2][2] = 1;
dp[2][1][2] = dp[2][2][1] = 0;
for(int i=3;i<100005;i++){
dp[i][0][0] = (dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2])%1000007;
dp[i][0][1] = (dp[i-1][0][0]+dp[i-1][0][1])%1000007;
dp[i][0][2] = (dp[i-1][0][0]+dp[i-1][0][2])%1000007;
dp[i][1][0] = (dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2])%1000007;
dp[i][1][1] = (dp[i-1][1][0]+dp[i-1][1][1])%1000007;
dp[i][1][2] = (dp[i-1][1][0]+dp[i-1][1][2])%1000007;
dp[i][2][0] = (dp[i-1][2][0]+dp[i-1][2][1]+dp[i-1][2][2])%1000007;
dp[i][2][1] = (dp[i-1][2][0]+dp[i-1][2][1])%1000007;
dp[i][2][2] = (dp[i-1][2][0]+dp[i-1][2][2])%1000007;
}
int n;cin>>n;
while(n--){
int a;cin>>a;
cout<<(dp[a][0][0]+dp[a][0][1]+dp[a][0][2]+dp[a][1][0]+dp[a][1][1]+dp[a][2][0]+dp[a][2][2])%1000007<<endl;
}
}
|