2013-09-16 08:12:16| 人氣1,079| 回應0 | 上一篇 | 下一篇

[UVA][dp] 11125 - Arrange Some Marbles

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

2 3 3

2 4 4

2 6 6

3 3 4 5

3 4 5 6

4 2 3 4 5

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

我要檢舉

#11125#Arrange Some Marbles

台長： Morris

您可能對以下文章有興趣

[UVA][maxflow、黑白染色] 10349 - Antenna Placement

[UVA][DP] 435 - Block Voting

[UVA] 838 - Worm World

[UVA][SPFA&DP][C++] 11813 - Shopping

人氣(1,079) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][排列組合] 11282 - Mixing Invitations
此分類上一篇:[UVA] 10307 - Killing Aliens in Borg Maze

回應(0)