SRM 584 Div Ii Level Three: Excavations2, Dynamic Programming

题目来源：http://community.topcoder.com/stat?c=problem_statement&pm=12644

这道题目其实就是个排列组合的问题，用数学的语言表述就是：

有n （found的大小）个箱子，每个箱子中有若干个不同的小球，箱子中的小球分别数量为a1, a2, a3, ...., an，

现要从这n个箱子中取K个小球，K>=n，且至少要从每个箱子中取一个小球，问有多少种取法？

如果你高中数学学的扎实的话，那应该可以推导出一个数学公式，就像这里（点击）这个大神给出的解释一

样，如果不幸你高中排列组合没有学好，那也不要紧，可以用 Dynamic Programming 的方法来解这个问题。

分析如下：

要求个n个箱子取K个小球的取法，先考虑从n－1个箱子中取球n－1到K－1个球的总的取法，最后再从最后一

个箱子中取1到 K - n + 1 个小球的取法，将其结果相乘，即可得到从n个箱子了取K个小球的全部取法。

代码如下：

#include <iostream>
#include <string>
#include <vector>

using namespace std;


/************** Program  Begin *********************/
#define MAX 51
int cnt[MAX];			// found中每个元素出现的次数
long long Cr[MAX][MAX];		// Cr[n][m] 表示从n个小球中选m个的不同选法
vector < double > sels(MAX);	// 最后的结果，sels[K]保存的程序要返回的值
vector < double > temp(MAX);	// 保存前一个步骤产生的结果

class Excavations2 {
public:
	long long count(vector <int> kind, vector <int> found, int K) 
	{	
		// 下面是对全局变量进行初始化
		for (int i = 0; i < MAX; i++) {
			cnt[i] = 0;
			sels[i] = 0;
			temp[i] = 0;
			for (int j = 0; j < MAX; j++) {
				Cr[i][j] = 0;
			}
		}

		// 下面是计算Cr数组的值，利用Cr[n][r] = Cr[n-1][r] + Cr[n-1][r-1]
		Cr[0][0] = 1;
		for (int i = 1; i < MAX; i++) {
			Cr[i][0] = 1;
			Cr[i][i] = 1;
			for (int j = 1; j < i; j++) {
				Cr[i][j] = Cr[i-1][j] + Cr[i-1][j-1];
			}
		}

		// 下面是计算fonud中每个元素出现的次数，结果保存在cnt数组中
		for (int i = 0; i < found.size(); i++) {
			cnt[i] = 0;
			for (int j = 0; j < kind.size(); j++) {
				if (found[i] == kind[j]) {
					++cnt[i];
				}
			}
		}
		
		// 下面是进行动态规划，step是表示只考虑found[step]及之前的元素
		for (int step = 0; step < found.size(); step++) {
			if (0 == step) {
				for (int i = 1; i <= cnt[step]; i++) {
					sels[i] = Cr[cnt[step]][i];
				}
				temp = sels;
			} else {
				for (int i = 0; i < MAX; i++) {
					sels[i] = 0;
				}
				for (int i = 1; i <= MAX; i++) {
					for (int j = 1; j <= MAX; j++) {
						if (i + j <= K) {
							sels[i+j] += temp[i] * Cr[cnt[step]][j];
						}
					}
				}
				temp = sels;
			}
		}

		return sels[K];
	}
};
/************** Program End ************************/