UVA11125 - Arrange Some Marbles（dp）

UVA11125 - Arrange Some Marbles（dp）

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;
}