题解 | 神奇的口袋

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> dp(41,0);
	dp[0] = 1;//容量为0时，方式为一种
	for (int i = 0; i < n; i++)cin >> a[i];
	for (int i = 0; i < n; i++) {
		for (int j = 40; j >= a[i]; j--) {
			//j代表物品的价值（容量）
			dp[j] = dp[j] + dp[j - a[i]];
		}
	}
	cout << dp[40];
}