题目地址:这里
题意:所有能组成K的C的子集方案中,能拼出哪些面额
解法:DP。n^3dpdp[i][j][k]表示用到了第i个数,当前和为j,子集和为k可不可行
裸的会稍微卡一下空间,这个滚动数组优化,或者直接用bool就可以了。我滚动数组优化的。
//CF 688E
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n, k;
int dp[2][maxn][maxn]; //dp[i][j][k]表示用到了第i个数,当前和为j,子集和为k可不可行
int now = 0, pre = 1;
int main(){
scanf("%d%d", &n, &k);
dp[0][0][0] = 1;
for(int i = 1; i <= n; i++){
swap(now, pre);
int x;
scanf("%d", &x);//对于x选和不选,分当前和和子集和两种
for(int j = 0; j <= 500; j++){
for(int k = 0; k <= j; k++){
dp[now][j][k] |= dp[pre][j][k];
if(j >= x) dp[now][j][k] |= dp[pre][j-x][k];
if(j >= x && k >= x) dp[now][j][k] |= dp[pre][j-x][k-x];
}
}
}
vector <int> ans;
for(int i = 0; i <= 500; i++){
if(dp[now][k][i]) ans.push_back(i);
}
printf("%d\n", ans.size());
for(int i = 0; i < ans.size(); i++){
printf("%d ", ans[i]);
}
}