给定一个货币系统,包含n种面值的货币,你需要计算组成面值为m的货币有多少种方案。

输入格式

  • 第一行:两个整数n和m,表示货币种类数和目标面值。
  • 接下来n行:每行包含一个整数,表示一种货币的面值。

输出格式

  • 一行:一个整数,表示组成面值为m的货币的方案数。

数据范围

  • 1 ≤ n ≤ 15
  • 1 ≤ m ≤ 3000

输入样例

3 10
1
2
5

输出样例

10

题目分析

完全背包

代码实现

#include <iostream>
using namespace std;
using ll = long long;
const int N = 3e3 + 10;

ll n, v, V, dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> V;
    dp[0] = 1;
    while(n--) {
        cin >> v;
        for (int i = 0; i <= V; ++i) if (i >= v) dp[i] += dp[i - v];
    }
    cout << dp[V];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status