1068. Find More Coins (30)

2019-11-14 10:16:51

字体：大中小

来源：转载

供稿：网友

1068. Find More Coins (30) 考察动态规划

#include <iostream>#include <vector>#include <algorithm>using namespace std;const int MAXN=10004,MAXM=104;int n,m;int v[MAXN],dp[MAXN][MAXM];bool flag[MAXN][MAXM];int main(){ cin>>n>>m; for(int i=1;i<=n;++i) cin>>v[i]; sort(v+1,v+n+1,greater<int>()); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { if(j<v[i]||dp[i-1][j-v[i]]+v[i]<dp[i-1][j]) dp[i][j]=dp[i-1][j]; else { dp[i][j]=dp[i-1][j-v[i]]+v[i]; flag[i][j]=true; } } } if(dp[n][m]!=m) cout<<"No Solution"; else { vector<int> ans; while(m) { while(!flag[n][m])--n; ans.push_back(v[n]); m-=v[n--]; } for(auto it=ans.begin();it!=ans.end();++it) (it==ans.end()-1)?cout<<*it:cout<<*it<<" "; } return 0;}

上一篇：[Educational Codeforces Round 17 D (762D)] Maximum path

下一篇：线程基本编程——线程函数大全