AcWing 1371. 货币系统
原题链接
简单
作者:
术
,
2021-05-19 16:59:50
,
所有人可见
,
阅读 244
1.朴素做法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e4+5;
int a[N];
long long dp[26][N];
int main()
{
int v,n;
cin>>v>>n;
for(int i=1; i<=v; i++) cin>>a[i];
dp[0][0]=1;
for(int i=1;i<=v;i++){
for(int j=0;j<=n;j++){
for(int k=0;a[i]*k<=j;k++){
dp[i][j]+=dp[i-1][j-k*a[i]];
}
}
}
cout<<dp[v][n];
//ciout << "Hello world!" << endl;
return 0;
}
2.一维优化
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e4+5;
int a[N];
long long dp[N];
int main()
{
int v,n;
cin>>v>>n;
for(int i=1; i<=v; i++) cin>>a[i];
dp[0]=1;
for(int i=1;i<=v;i++){
for(int j=a[i];j<=n;j++){
dp[j]+=dp[j-a[i]];
}
}
cout<<dp[n];
//ciout << "Hello world!" << endl;
return 0;
}