AcWing 1371. 货币系统
原题链接
简单
作者:
Anoxia_3
,
2021-01-23 12:33:28
,
所有人可见
,
阅读 341
朴素做法
#include <iostream>
using namespace std;
const int N = 10010;
int n , m;
long long a[30] , f[30][N];
//f[i][j]表示从前i个数中选,结果等于j的方案数
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
//初始化边界,从前i个数中选,结果为0的方案数都是1
for(int i = 0 ; i <= n ; i++) f[i][0] = 1;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
{
f[i][j] = f[i - 1][j];//不选第i个数
for(int k = 1 ; k * a[i] <= j ; k++)//选第i个数,并枚举个数
f[i][j] += f[i - 1][j - a[i] * k];
}
cout << f[n][m] << endl;
}
优化一重循环
#include <iostream>
using namespace std;
const int N = 10010;
int n , m;
long long a[30] , f[30][N];
//f[i][j]表示从前i个数中选,结果等于j的方案数
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
//初始化边界,从前i个数中选,结果为0的
for(int i = 0 ; i <= n ; i++) f[i][0] = 1;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= m ; j++)
{
f[i][j] = f[i - 1][j];//不选第i个数
if(j - a[i] >= 0)
f[i][j] += f[i][j - a[i]];
/*
因为f[i][j] = f[i - 1][j] + f[i - 1][j - v] + f[i - 1][j - 2v] + ... + f[j - kv];
f[i][j - v] = f[i - 1][j - v] + f[i - 1][j - 2v] + ... + f[j - kv];
所以f[i][j] = f[i - 1][j] + f[i][j - v];
*/
}
cout << f[n][m] << endl;
}
优化掉一维
#include <iostream>
using namespace std;
const int N = 10010;
int n , m;
long long a[30] , f[N];
//f[j]表示从前i个数中选,结果等于j的方案数
int main()
{
cin >> n >> m;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
f[0] = 1;
for(int i = 1 ; i <= n ; i++)
for(int j = a[i] ; j <= m ; j++)
f[j] += f[j - a[i]];
cout << f[m] << endl;
}