AcWing 1371. 货币系统
原题链接
简单
作者:
一抹斜阳
,
2021-01-23 12:09:53
,
所有人可见
,
阅读 330
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int v,n;
const int N = 30,M = 1e4 + 10;
long long dp[N][M];
int a[N];
int main(){
cin>>v>>n;
unordered_map<int,int> mp;
int t = 0;
//去重
for(int i = 0;i < v;i++){
cin>>t;
if(mp.count(t) == 0) mp[t]++;
}
int j = 0;
for(auto x : mp){
a[j++] = x.first;
v = j;
}
sort(a,a + v);
dp[0][0] = 1;
for(int i = 0;i < v;i++) dp[i][0] = 1;
for(int j = 1;j <= n;j++ )
if(j % a[0] == 0) dp[0][j] = 1;
else dp[0][j] = 0;
for(int i = 1;i < v;i++)
for(int j = 1;j <= n;j++)
for(int k = 0;j >= k * a[i];k++)
dp[i][j] += dp[i - 1][j - k * a[i]];
cout<<dp[v - 1][n]<<endl;
return 0;
}