UVA 11125 Arrange Some Marbles

dp[i][j][m][n][s]表示最初选择j个i号颜色大理石。当前选择n个m号颜色大理石。剩余大理石状态（8进制数状压表示）最开始没看出状压。。sad

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <ctime>

#include <deque>

#include <stack>

#include <queue>

#include <cctype>

#include <cstdio>

#include <string>

#include <vector>

#include <climits>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define PI 3.1415926535897932626

using namespace std;

int gcd(int a, int b) {return a % b ==  ? b : gcd(b, a % b);}

int base_8[]={ , , ,};

int cnt[],dp[][][][][];

int N;

int calcu(int hc, int hl, int pc, int pl, int sta)

{

    if (dp[hc][hl][pc][pl][sta]!=-) return dp[hc][hl][pc][pl][sta];

    dp[hc][hl][pc][pl][sta]=;

    if (sta == )

    {

        if (hc != pc && hl != pl) return dp[hc][hl][pc][pl][sta] = ;

        else return dp[hc][hl][pc][pl][sta] = ;

    }

    for (int i = ; i < N; i++)

        for (int j = ; j <=  && j <= cnt[i]; j++)

    {

        if (i != pc && j != pl)

        {

            cnt[i] -= j;

            dp[hc][hl][pc][pl][sta] += calcu(hc, hl, i, j, sta - base_8[i] * j);

            cnt[i] += j;

        }

    }

    return dp[hc][hl][pc][pl][sta];

}

int slove()

{

    int state=,ans=;

    for (int i = N - ; i >= ; i--) state = state *  + cnt[i];

    for (int i = ; i < N; i++)

        for (int j = ; j <=  && j <= cnt[i]; j++)

    ans += calcu(i, j, i, j,state - j * base_8[i]);

    return ans;

}

int main()

{

    int T;

    memset(dp,-,sizeof(dp));

    scanf("%d",&T);

    while (T--)

    {

        scanf("%d",&N);

        for (int i = ; i < N; i++) scanf("%d",&cnt[i]);

        if (cnt[] ==  && cnt[] ==  && cnt[] ==  && cnt[] == ) puts("");

        else  printf("%d\n",slove());

    }

    return ;

}