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 87 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个55dp[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; }

总结

以上是生活随笔为你收集整理的ARC-060C - Tak and Cards - 动态规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。