CSES – Money Sums

背包問題

#include<bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int n;
bool dp[maxn];
vector<int> v;
//
signed main(){
    fastio;
    cin>>n;
    for(int i=0;i<n;i++){
        int x; cin>>x;
        v.push_back(x);
    }
    dp[0] = 1;
    for(int i=0;i<n;i++){
        for(int j=maxn-1;j>=0;j--){
            if(j-v[i] >= 0) dp[j] |= dp[j-v[i]];
        }
    }
    vector<int> ans;
    for(int i=1;i<maxn;i++){
        if(dp[i]) ans.push_back(i);
    }
    cout<<ans.size()<<"\n";
    for(int i:ans) cout<<i<<" ";
    cout<<"\n";
    return 0;
}

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *