Codeforces Round #360 (Div. 2) E. The Values You Can Make dp ,滚动数组

时间:2022-06-11 18:42:07

题目地址:这里
题意:所有能组成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]);
    }
}