P2842 纸币问题 1

题目描述

某国有 n 种纸币，每种纸币面额为 ai​ 并且有无限张，现在要凑出 w 的金额，试问最少用多少张纸币可以凑出来？（保证可以凑出对应金额）

输入格式

第一行两个整数 n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的整数 a1​,a2​,a3​,…an​ 依次表示这 n 种纸币的面额。

输出格式

一行一个整数，表示最少使用的纸币张数。

输入输出样例

输入 #1复制

6 15
1 5 10 20 50 100

输出 #1复制

2

输入 #2复制

3 15
1 5 11

输出 #2复制

3

说明/提示

对于 40% 的数据，满足 n≤10，w≤100；
对于 100% 的数据，满足 1≤n≤103，1≤ai​,w≤104。

实现代码：

#include<bits/stdc++.h>
using namespace std;
long long n,w,a[1010],f[100010];
int main(){
	cin>>n>>w;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=10010;i++)f[i]=1145141919;
	for(int i=1;i<=n;i++)
		for(int j=a[i];j<=w;j++)
			f[j]=min(f[j],f[j-a[i]]+1);
	cout<<f[w]<<endl;
	return 0;
} 

P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中，从 7→3→8→7→5 的路径产生了最大权值。

输入格式

第一个行一个正整数 r，表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行，包含那个可能得到的最大的和。

输入输出样例

输入 #1复制

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 

输出 #1复制

30

说明/提示

【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。

题目翻译来自 NOCOW。

IOI1994 Day1T1 / USACO Training Section 1.5。

 实现代码：

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			a[i][j]=max(a[i-1][j],a[i-1][j-1])+a[i][j];
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum=max(sum,a[n][i]);
	}
	cout<<sum;
	return 0;
}

P2840 纸币问题 2

题目背景

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

题目描述

你有 n 种面额互不相同的纸币，第 i 种纸币的面额为 ai​ 并且有无限张，现在你需要支付 w 的金额，求问有多少种方式可以支付面额 w，答案对 109+7 取模。
注意在这里，同样的纸币组合如果支付顺序不同，会被视作不同的方式。例如支付 3 元，使用一张面值 1 的纸币和一张面值 2 的纸币会产生两种方式（1+2 和 2+1）。

输入格式

第一行两个正整数 n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的正整数 a1​,a2​,…an​ 依次表示这 n 种纸币的面额。

输出格式

一行一个整数，表示支付方式的数量。

输入输出样例

输入 #1复制

6 15
1 5 10 20 50 100

输出 #1复制

42

输入 #2复制

3 15
1 5 11

输出 #2复制

39

说明/提示

对于 40% 的数据，满足 n≤10，w≤100；
对于 100% 的数据，满足 1≤n≤103，1≤ai​,w≤104。

其实小朋友并没有那么多钱。

 实现代码：

#include<iostream>
using namespace std;
int n,w,a[1005],f[10005];
const int mod=1e9+7;
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    f[0]=1;
    for(int i=1;i<=w;i++){
        for(int j=1;j<=n;j++){
            if(i-a[j]>=0){
                f[i]=(f[i]+f[i-a[j]])%mod;
            }
        }
    }
    cout<<(f[w]%mod)<<endl;
    return 0;
}

P2834 纸币问题 3

题目背景

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

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

题目描述

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

输入格式

第一行两个正整数 n,w，分别表示纸币的种数和要凑出的金额。
第二行一行 n 个以空格隔开的正整数 a1​,a2​,…an​ 依次表示这 n 种纸币的面额。

输出格式

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

输入输出样例

输入 #1复制

6 15
1 5 10 20 50 100

输出 #1复制

6

输入 #2复制

3 15
1 5 11

输出 #2复制

5

说明/提示

对于 40% 的数据，满足 n≤10，w≤100；
对于 100% 的数据，满足 1≤n≤103，1≤ai​,w≤104。

其实小朋友并不有钱。

 实现代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
const int W = 1e4 + 5;
const int inf = 2e9;
const int mod = 1e9 + 7;
int n,w;
int a[N];
int f[W];

int main() {
	cin>>n>>w;
	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<=w; j++) {
			f[j] += f[j - a[i]] % mod;
			f[j] %= mod;
		}
	}
	cout<<f[w]<<endl;
	return 0;
}

P1048 [NOIP 2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 2 个整数 T（1≤T≤1000）和 M（1≤M≤100），用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。

接下来的 M 行每行包括两个在 1 到 100 之间（包括 1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

输入输出样例

输入 #1复制

70 3
71 100
69 1
1 2

输出 #1复制

3

说明/提示

【数据范围】

• 对于 30% 的数据，M≤10；
• 对于全部的数据，M≤100。

【题目来源】

NOIP 2005 普及组第三题

  实现代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int t,m;
int v[N],x[N];
int f[N];

int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>v[i]>>x[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=t;j>=v[i];j--){
			f[j]=max(f[j],f[j-v[i]]+x[i]);
		}
	}
	cout<<f[t];
	return 0;
}