[SCOI2008]着色方案(DP)

题目链接

思想

显然我们后面的决策是跟前一步相关的，因此我们可以考虑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;
}

本文地址：https://blog.csdn.net/weixin_45483201/article/details/107406208