ARC-060C - Tak and Cards - 动态规划

题目描述
Tak has N cards. On the i-th (1≤i≤N) card is written an integer xi. He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A. In how many ways can he make his selection?

Constraints
1≤N≤50
1≤A≤50
1≤xi≤50
N,A,xi are integers.
Partial Score
200 points will be awarded for passing the test set satisfying 1≤N≤16.

输入
The input is given from Standard Input in the following format:
N A
x1 x2 … xN

输出
Print the number of ways to select cards such that the average of the written integers is exactly A.

样例输入

4 8
 7 9 8 9

样例输出

5

提示
The following are the 5 ways to select cards such that the average is 8:
Select the 3-rd card.
Select the 1-st and 2-nd cards.
Select the 1-st and 4-th cards.
Select the 1-st, 2-nd and 3-rd cards.
Select the 1-st, 3-rd and 4-th cards.

题意
  给你N张卡片，每个卡片有一个权值，然你选任意多张卡片（不能为0），使得这些卡片权值的平均值严格等于A，问你有多少种选法。

思路：

先将题目的平均数转化为i个数的和是A的i倍。如此之后就可以考虑用动态规划的方法来求解。因为数据范围小，所以从小到大枚举计算，最后找出倍数。

dp[i][k] 的含义是前i的数和为k的个数。

代码

int main() {
	while (cin >> n >> A) {
		ans = 0;
		mem(dp, 0);
		for (int i = 1; i <= n; ++i)
			cin >> a[i];
		dp[0][0] = 1;
		for (int i = 1; i <= n; ++i) {
			int  x = a[i];
			for (int j = i - 1; j >= 0; --j)// 分别加1个，2.。。i-1 个 两两组合的个数，只不过前边有记录
				for (int k = 0; k <= 55 * j; k++) //枚举与前边数的和因为最大的和也就是j个55
					dp[j + 1][k + x] += dp[j][k]; // 如果前边有 dp[j][k] 个数只要 k+x == A 那么 dp[j+1][A] = dp[j][k]
		}
		for (int i = 1; i <= n; ++i)
			ans += dp[i][A * i];  //当所有的数均是A是倍数是最大有效的
		cout << ans << endl;
	}
	return 0;
}