UVA11125 - Arrange Some Marbles（dp）

题目链接

题目大意：给你n种不同颜色的弹珠，然后给出每种颜色的弹珠的个数，现在要求你将这些弹珠排序，要求相同颜色的部分最多3个。然后相同颜色的弹珠称为一个组，那么每个相邻的组要求长度不同，颜色也不同，然后首位的两组也要符合要求。

解题思路：这题之前是被n<3000给吓到了，后面dp还那么多状态，感觉复杂度不能过。后面看了题解才发现dp的时候会将所有的情况包括进去，所以只要dp的数组的复杂度够就行了，和n没有关系。因为这题有给弹珠的数目，所以需要记录一下每种颜色的弹珠的剩余数目，那么就是8 8 8 8.（可以用一个8进制的数来代替传4个参数）因为还要求相邻的颜色和长度不同，所以还要3 4来存放上一次是什么颜色长度是多少。麻烦的是首尾怎么办。枚举出首的组那么对应的尾也就好处理了。所以再开3 4将第一个的颜色和大小存储进去。这样复杂度就是8 8 8 8 144。注意：0的时候输出的是1.
为什么和n没有关系呢，因为题目变动的只是颜色的数目和各个颜色的个数，而我们dp的时候是将会出现的四种颜色，会出现的所有个数都包括进去了。

代码：

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 4500; const int maxs = 5; const int maxc = 5; int N, PS, PC; int num[maxc]; int f[maxn][maxs][maxc][maxs][maxc]; int dp (int state, int s, int c) { int& ans = f[state][PS][PC][s][c]; if (ans != -1) return ans; if (!state) { if (PS != s && PC != c) return ans = 1; return ans = 0; } int tmp[maxc]; int tS = state; for (int i = N - 1; i >= 0; i--) { if (tS >= (1<<(3*i))) { tmp[i] = tS/(1<<(3*i)); tS %= (1<<(3*i)); } else tmp[i] = 0; } ans = 0; for (int i = 0; i < N; i++) { if (i == c) continue; for (int j = 1; j <= min(3, tmp[i]); j++) { if (j == s) continue; ans += dp(state - (j * (1<<(3*i))), j, i); } } return ans; } void solve () { scanf ("%d", &N); for (int i = 0; i < N; i++) scanf ("%d", &num[i]); int state = 0; for (int i = 0; i < N; i++) state += num[i] * (1<<(3*i)); int ans = 0; if (state) { for (int c = 0; c < N; c++) for (int s = 1; s <= min(num[c], 3); s++) { PS = s; PC = c; ans += dp(state - s * (1<<(3*c)), s, c); } } else ans = 1; printf ("%d\n", ans); } int main () { int T; scanf ("%d", &T); memset (f, -1, sizeof(f)); while (T--) { solve(); } return 0; }