UVA11125 - Arrange Some Marbles（dp）

option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2066" target="_blank" style="">题目链接

题目大意：给你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 <cstdio>

#include <cstring>

#include <algorithm>

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;

}