[UVA][dp] 11125 - Arrange Some Marbles
Problem H
Arrange Some Marbles
Input: Standard Input
Output: Standard Output
you are given some marbles of n different color. You have to arrange these marbles in a line. The marbles adjacent with same color form a group. In each group there can be 1 to 3 marble. Adjacent group should have different color and size. The first and last group also should have different color and size. You are given the number of each of these n marbles. You have count the number of ways you can arrange them in a line maintaining the above constraints. For example you have 4 red marbles and 4 green marbles. You can arrange them in the following 8 way - GGGRRGRR, GGRGGRRR, GGRRRGGR, GRRGGGRR, RGGRRRGG, RRGGGRRG, RRGRRGGG, RRRGGRGG.
Input
Input contains multiple number of test cases. The first line contain the number of test cases t (t<3000). Each of the next line contains one test case. Each test case starts with n (1 ≤ n ≤ 4) the number of different color. Next contains n integers. The i'th integer denotes the number of marble of color i. The number of marbles of any color is within the range 0..7 (inclusive). The color of the marbles are numbered from 1 to n.
Output
For each test case output contains one integer in one line denoting the number of ways you can arrange the marbles.
Sample Input Output for Sample Input
|
6 2 3 3 2 4 4 2 6 6 3 3 4 5 3 4 5 6 4 2 3 4 5 |
0 8 12 174 1234 1440
|
Problem-setter: Abdullah al Mahmud
Special Thanks: Mohammad Sajjad Hossain
每次放置相同顏色的彈珠，每團最多 1~3 顆，且相鄰不可同色，同時最後一團與第一團的顏色和個數都要不同。
給定每種顏色的彈珠個數，問有多少種排列方法。
題目解法：
由於最多四種顏色，每種最多 0~7 顆。
因此狀態有 8*8*8*8。
又考慮第一團與最後一團的顏色個數，因此多 *8*4*8*4。
每次考慮在排列中的最前方增加新的一團。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[8][8][8][8][4][3][4][3];
int dfs(int n[], int bcolor, int bsize, int lastcolor, int lastsize) {
//printf("%d %d %d %d\n", n[0], n[1], n[2], n[3]);
if(n[0]+n[1]+n[2]+n[3] == 0) {
return bcolor != lastcolor && bsize != lastsize;
}
if(bcolor != -1 && dp[n[0]][n[1]][n[2]][n[3]][bcolor][bsize][lastcolor][lastsize] != -1)
return dp[n[0]][n[1]][n[2]][n[3]][bcolor][bsize][lastcolor][lastsize];
int ret = 0;
int i, j;
for(i = 0; i < 4; i++) {
if(i == bcolor) continue;
for(j = 1; j <= 3; j++) {
if(j-1 == bsize) continue;
if(n[i] < j) continue;
n[i] -= j;
if(bcolor == -1)
ret += dfs(n, i, j-1, i, j-1);
else
ret += dfs(n, i, j-1, lastcolor, lastsize);
n[i] += j;
}
}
if(bcolor != -1)
dp[n[0]][n[1]][n[2]][n[3]][bcolor][bsize][lastcolor][lastsize] = ret;
return ret;
}
int main() {
memset(dp, -1, sizeof(dp));
int testcase;
int i, j, k, n, c[4];
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &c[i]);
for(i = n; i < 4; i++)
c[i] = 0;
int ret = dfs(c, -1, -1, -1, -1);
if(c[0]+c[1]+c[2]+c[3] == 0)
ret = 1;
printf("%d\n", ret);
}
return 0;
}