A40961. 神奇的小丑
填空题
较难
知识点
题目描述
神奇的小丑
题目描述
有一个神奇的小物件，现在这个总物品是 40 件，用起来可以变出几件物品，这些物品的总体积是 40 件。，一个2 …… 一个约翰 约翰 可以从中选择一些神奇的事物，可以从这些物体的总体积中选择 4个，如果是这些事物的神奇的总体积，约翰就可以揭穿约翰就得到了物品。现在约翰有多少种不同的选择物品的方式。
输入
输入的第一行是正n n <= 2 (0) 个不同的项目。表示每行有一个行到40行的正1，分别给出一个1， a 2 ……一个n的值。
输出
输出的选择物品的不同方式。
样例输入
3
20
20
20
样例输出
3
参考答案
#include<iostream>
#include<cstring>
using namespace std;
int a[30], N;
int ways[50][40];
int main() {
while(cin >> N) {
memset(ways, 0, sizeof(ways));
for(int i = 1; i <= N; i++) {
cin >> a[i];
ways[0][i] = 1;//用i个物品凑0体积的办法只有一种，那就是不选
}
//同理，把way[0][0]边界也设为 1
ways[0][0] = 1;
//w 代表需要凑成的体积， k代表第 k的物品， way[w][k]用来存储 k个物品凑成 w体积的方法个数
//要求way[w][k]，只要考虑第 k个物品取不取
//所以way[w][k] = way[w - a[k]][k-1] + way[w][k-1]
for(int w = 1; w <= 40; w++) {
for(int k = 1; k <= N; k++) {
ways[w][k] = ways[w][k-1];
if(w - a[k] >= 0)
ways[w][k] += ways[w-a[k]][k-1];
}
}
//所以本体所求即为N件物品凑成40体积的方法数
cout << ways[40][N] << endl;
}
return 0;
}
上一题
下一题