AcWing 1371. 货币系统
原题链接
简单
作者:
ofs
,
2024-04-11 23:38:16
,
所有人可见
,
阅读 2
//实际就是完全背包问题
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define endl "\n"
using namespace std;
const int N=30,M=10010;//货币数量与(宝物价值)总金额(背包容量)
int n,m;
int v[N];//(货币面值,相当于宝物的体积) 没有宝物的体积
int f[N][M];
//不优化
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i];
f[0][0]=1;//赋初值!!!
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
f[i][j]+=f[i][j-v[i]];
}
}
/*优化
int n,m;
int v[N];//(货币面值,相当于宝物的体积) 没有宝物的体积
int f[M];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i];
f[0]=1;//赋初值!!!
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=m;j++)
{
f[j]+=f[j-v[i]];
}
}
cout<<f[m];
return 0;
}
*/
cout<<f[n][m];
return 0;
}