題目描述
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 - 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。