洛谷纸币问题123
题目链接：
P2842 纸币问题 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P2840 纸币问题 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P2834 纸币问题 3 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
纸币问题1
题目描述
某国有 n 种纸币，每种纸币面额为 ai 并且有无限张，现在要凑出 w 的金额，试问最少用多少张纸币可以凑出来？
输入格式
第一行两个整数 ,n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的整数 a1,a2,a3,…an 依次表示这 n 种纸币的面额。输出格式
一行一个整数，表示最少使用的纸币张数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
void solve() {int dp[10001];memset(dp,0,sizeof(dp));//dp[amount]=min(dp[amount-amount[1-5])int amount[1001];int n,money;cin>>n>>money;for(int i=1;i<=n;i++){cin>>amount[i];dp[amount[i]]=1;}for(int i=1;i<=money;i++){for(int j=1;j<=n;j++){if(i>=amount[j]){if(dp[i]!=0&&dp[i-amount[j]]!=0){dp[i]=min(dp[i],dp[i-amount[j]]+1);}else if(dp[i-amount[j]]!=0){dp[i]=dp[i-amount[j]]+1;}}}}cout<<dp[money];
} signed main() {ll t = 1; // std::cin >> t;while (t--) {solve();}
}纸币问题2
题目描述
你有 n 种面额互不相同的纸币，第 i 种纸币的面额为 ai 并且有无限张，现在你需要支付 w 的金额，求问有多少种方式可以支付面额 w，答案对 10e9+7 取模。
注意在这里，同样的纸币组合如果支付顺序不同，会被视作不同的方式。例如支付 3 元，使用一张面值 1 的纸币和一张面值 2 的纸币会产生两种方式（1+2 和2+1）。输入格式
第一行两个正整数n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的正整数 a1,a2,…an 依次表示这 n 种纸币的面额。输出格式
一行一个整数，表示支付方式的数量。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
void solve() {ll sum=1e9+7;ll dp[100001];memset(dp,0,sizeof(dp));//dp[amount]=min(dp[amount-amount[1-5])ll amount[10001];int n,money;cin>>n>>money;for(int i=1;i<=n;i++){cin>>amount[i];dp[amount[i]]=1;}for(int i=0;i<=money;i++){for(int j=1;j<=n;j++){ dp[i+amount[j]]+=dp[i];if(dp[i+amount[j]]>=sum){dp[i+amount[j]]%=sum;}}}cout<<dp[money];
} signed main() {ll t = 1; // std::cin >> t;while (t--) {solve();}
}纸币问题3
题目描述
你有 n 种面额互不相同的纸币，第 i 种纸币的面额为 ai 并且有无限张，现在你需要支付 w 的金额，请问有多少种纸币组合能恰好支付金额 w，答案对 10e9+7 取模。
输入格式
第一行两个正整数n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的正整数 a1,a2,…an 依次表示这 n 种纸币的面额。输出格式
一行一个整数，表示能恰好凑齐面额 w 的纸币组合数量。
#include<bits/stdc++.h>using namespace std;#define ll long long #define ull unsigned long longint n,m;void solve() {cin>>n>>m;int dp[n+1];// 剩余时间中的最大价值 fill(dp,dp+n+1,0);int dp1[n+1];//或者有n时间下的最大价值fill(dp1,dp1+n+1,0);for(int i=1;i<=m;i++){int o1,o2;cin>>o1>>o2;if(o1<=n){for(int j=o1;j<=n;j++){dp[j-o1]=max(dp[j]+o2,dp[j-o1]);}for(int j=n;j>=o1;j--){dp1[j]=max(dp1[j-o1]+o2,dp1[j]) ;}}} //dp1更符合题意 sort(dp,dp+n+1);cout<<dp1[n];} signed main() {ll t = 1; //cin >> t;while (t--) {solve();}}