洛谷 P2834 纸币问题 3-普及-

题目背景

你是一个非常有钱的小朋友。

注意： 本题和《进阶篇》的对应题目，输入格式略有差异。

题目描述

你有 $n$ 种面额互不相同的纸币，第 $i$ 种纸币的面额为 $a_i$ 并且有无限张，现在你需要支付 $w$ 的金额，请问有多少种纸币组合能恰好支付金额 $w$，答案对 $10^9+7$ 取模。

输入格式

第一行两个正整数 $n,w$，分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的正整数 $a_1,a_2,\dots a_n$ 依次表示这 $n$ 种纸币的面额。

输出格式

一行一个整数，表示能恰好凑齐面额 $w$ 的纸币组合数量。

输入输出样例 #1

输入 #1

6 15
1 5 10 20 50 100

输出 #1

6

输入输出样例 #2

输入 #2

3 15
1 5 11

输出 #2

5

说明/提示

对于 $40\%$ 的数据，满足 $n\le 10$，$w\le 100$；
对于 $100\%$ 的数据，满足 $1\le n\le 10^3$，$1\le a_i,w\le 10^4$。

其实小朋友并不有钱。

solution

代码

#include<iostream>
#include "unordered_map"
#include "unordered_set"
#include "stack"
#include "queue"
#include "cstring"
#include "algorithm"using namespace std;
const int N = 1e3 + 5, INF = 1e4, M = 1e4 + 5, mod = 1e9 + 7;int a[N], n, w, f[M], g[M];int main() {cin >> n >> w;for (int i = 0; i < n; i++) cin >> a[i];f[0] = 1;for (int i = 0; i < n; i++) {for (int j = a[i]; j <= w; j++) {f[j] = (f[j] + f[j - a[i]]) % mod;}}cout << f[w];return 0;
}

结果