[UVA][dp] 12001 - UVa Panel Discussion
UVa Panel Discussion
| UVa Panel Discussion |
The UVa online judge team is arranging a panel discussion for the next ACM-ICPC World Finals event in Orlando, Florida. They want that three or four of the contestants take part in the panel and as they have about 300 persons for selecting such a little group, they have decided to put some restrictions in order to reduce the number of possibilities.
After thinking about several options, they finally propose that in case the number of contestants to choice be 3, all of them must be of the same country or from three different countries; and in case the number be 4, at least three of them will be of the same country or must be from at least three different countries.
Could you help them to calculate the number of different selections they can make following the restrictions above.
Input
The input file contains several test cases; each of them consists of two lines.
The first contains two integers N and M separated by one space. N (
3
N300) is the number of
contestants and M (
1M50) the total number of different countries. The second line consists of N
integers between 1 and M, separated by a space, representing the country each contestant is from (It is not
necessary that contestants will be from M countries).
Last line of the input will contain two zeroes and it won't be processed.
Output
For each input case write, in a line by itself, two integers separated by a space.
The first integer being be the number of ways to select a group of three people, and the second the number of ways to do it of four people.
Sample Input
3 5 5 4 2 5 3 3 1 3 2 2 10 10 1 8 9 1 6 7 3 4 10 4 0 0
Sample Output
1 0 4 4 104 209
題目解法：
dp[i][j][k] 表示放入 i 個人，分組中有 j 個國家，k 個人。
特別考慮 ooxx 的錯誤轉移。
#include <stdio.h>
#include <string.h>
int main() {
int n, m, x;
int i, j, k;
int C[305][5] = {};
C[0][0] = 1;
for(i = 1; i <= 300; i++) {
C[i][0] = 1;
for(j = 1; j <= i && j < 5; j++) {
C[i][j] = C[i-1][j]+C[i-1][j-1];
}
}
while(scanf("%d %d", &n, &m) == 2 && n+m) {
int country[55] = {};
for(i = 0; i < n; i++) {
scanf("%d", &x);
country[x]++;
}
int dp[55][5][5] = {};
dp[0][0][0] = 1;
for(i = 1; i <= m; i++) {
dp[i][0][0] = 1;
for(j = 1; j <= 4; j++) {//different country.
for(k = 1; k <= 4; k++) {//people
dp[i][j][k] = dp[i-1][j][k];
if(k-1 >= 0)
dp[i][j][k] += dp[i-1][j-1][k-1]*C[country[i]][1];
if(k-2 >= 0 && !(j-1 == 1 && k-2 == 2))
dp[i][j][k] += dp[i-1][j-1][k-2]*C[country[i]][2];
if(k-3 >= 0)
dp[i][j][k] += dp[i-1][j-1][k-3]*C[country[i]][3];
if(k-4 >= 0)
dp[i][j][k] += dp[i-1][j-1][k-4]*C[country[i]][4];
}
}
}
int ret3 = dp[m][1][3]+dp[m][3][3];
int ret4 = dp[m][1][4]+dp[m][2][4]+dp[m][3][4]+dp[m][4][4];
printf("%d %d\n", ret3, ret4);
}
return 0;
}
/*
10 10
1 1 3 4 4 6 7 8 9 10
*/