題目鏈接

思想

顯然我們后面的決策是跟前一步相關的，因此我們可以考慮DP，可以用一個15維的數組來進行轉移，但是這樣顯然回mle，所以我們考慮如何壓縮狀態，由于$1<=C_i<=5$，所以我們可以有dp數組:
$dp[a_1][a_2][a_3][a_4][a_5][last]$，$a_1$表示可以涂1塊木塊的有多少種顏色，以此類推，$last$表示上一次用的是可以涂$last$個木塊的顏色。

接下來就是考慮dp方程的轉移了。
舉個例子：
假設上一次用的顏色是可以涂5個塊的，那么下一步的狀態轉移就會變成：
$sum=a_1?dp[a_1?1][a2][a3][a_4][a_5][1]+a_2?dp[a_1+1][a_2?1][a_3][a_4][a_5][2]+a_3?dp[a_1][a_2+1][a_3?1][a_4][a_5][3]+(a4?1)?dp[a_1][a_2][a_3+1][a_4?1][a_5][4]+a5?dp[a_1][a_2][a_3][a_4+1][a_5?1][5]$

之所以$a_4?1$是因為，上一步選的是5，所以轉移過來的時候$a_4+1$，這里面有一個是跟上一個塊同顏色的，所以需要減去，其他情況同理。

考慮到數據比較小，并且這個dp方程有點難轉移，因此我們可以考慮用記憶化搜索來進行dp轉移。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }void print(ll x) {if(x < 10) {putchar(x + 48);return ;}print(x / 10);putchar(x % 10 + 48); }const int mod = 1e9 + 7;ll dp[20][20][20][20][20][10]; int n, a[10];ll dfs(int a1, int a2, int a3, int a4, int a5, int last) {if(dp[a1][a2][a3][a4][a5][last]) return dp[a1][a2][a3][a4][a5][last];ll ans = 0;if(a1) ans = (ans + 1ll * (a1 - (last == 2)) * dfs(a1 - 1, a2, a3, a4, a5, 1)) % mod;if(a2) ans = (ans + 1ll * (a2 - (last == 3)) * dfs(a1 + 1, a2 - 1, a3, a4, a5, 2)) % mod;if(a3) ans = (ans + 1ll * (a3 - (last == 4)) * dfs(a1, a2 + 1, a3 - 1, a4, a5, 3)) % mod;if(a4) ans = (ans + 1ll * (a4 - (last == 5)) * dfs(a1, a2, a3 + 1, a4 - 1, a5, 4)) % mod;if(a5) ans = (ans + 1ll * a5 * dfs(a1, a2, a3, a4 + 1, a5 - 1, 5)) % mod;return dp[a1][a2][a3][a4][a5][last] = ans; }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read();for(int i = 1; i <= n; i++) {int x = read();a[x]++;}for(int i = 1; i <= 5; i++) dp[0][0][0][0][0][i] = 1;print(dfs(a[1], a[2], a[3], a[4], a[5], 0));return 0; }

總結

以上是生活随笔為你收集整理的[SCOI2008]着色方案(DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。