时间：1s 空间：128M
题目描述：
一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1, W2, ..., Wn，它们的价值分别为C1, C2, ..., Cn。若每种物品只有一件，求旅行者能获得的最大总价值。
输入格式：
第一行：两个整数，M(背包容量，M<=200) 和 N(物品数量，N<=30)；
第2...N+1行：每行二个整数 Wi, Ci，表示每个物品的重量和价值。
输出格式：
仅一行，一个数，表示最大总价值
样例输入：
10 4
2 1
3 3
4 5
7 9
样例输出：
12 #include<bits/stdc++.h> using namespace std; int m, n; int w[205], c[205]; int f[205]; int main(){ scanf("%d%d",&m, &n); for (int i=1; i <= n; i++) scanf("%d%d",&w[i],&c[i]); for (int i=1; i <= n; i++) for (int v = m; v >= w[i]; v--) if (f[v-w[i]]+c[i]>f[v]) f[v] = f[v-w[i]]+c[i]; printf("%d",f[m]); return 0; } B. 采药题目描述：
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式：
第一行有2个整数T(1≤T≤1000)和M(1≤M≤100)，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。
接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式：
1个整数，表示在规定的时间内可以采到的草药的最大总价值。
样例输入1：
70 3
71 100
69 1
1 2
样例输出1：
3
#include <bits/stdc++.h> using namespace std; int dp[1000000]; int a[10100]; int v[10100]; int main(){ int t,m; cin>>t>>m; for(int i=1; i<=m; i++){ cin>>v[i]>>a[i]; } for(int i=1; i<=m; i++){ for(int j=t; j>=v[i]; j--){ dp[j]=max(dp[j],dp[j-v[i]]+a[i]); } } cout<<dp[t]; return 0; } C. 选取整数题目描述
从 1 到 n 中选择若干个数，它们的总和不超过 n。 每个选择的数字都有自己的约数个数。
将这些数的约数个数相加，您可以得到一个总和。 找出这些所选数字的最大约数个数总和。
注意：这个总和不是那些选择的数字的总和，而是约数个数的总和。
输入样例
2输出样例
2数据约定
n<=1000
时间和空间约定
1s ，512M
#include<bits/stdc++.h> using namespace std; int sum[1010],dp[1010]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ if(i%j==0){ sum[i]++; } } } for(int i = 1;i <=n; i++){ for(int j = n ; j>= i; j--){ dp[j] = max(dp[j],dp[j-i] + sum[i]); } } cout<<dp[n]; return 0; } D. noip2001普及组 4.装箱问题时间：1s 空间：128M
题目描述：
有一个箱子容量为V（正整数，0≤V≤20000），同时有n个物品（ 0<n≤30 )，每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式：
1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积
输出格式：
1个整数，表示箱子剩余空间。
样例输入1：
24
6
8
3
12
7
9
7
样例输出1：
0
说明：NOIp2001普及组 第4题
#include<bits/stdc++.h> int dp[20005]; int box[40]; int max(int a,int b){ if(a>=b) return a; return b; } int main(){ int v,n; scanf("%d%d",&v,&n); for(int i = 0;i<n;i++){ scanf("%d",&box[i]); } for(int i = 0;i < n; i++){ for(int j = v ; j>= box[i]; j--){ dp[j] = max(dp[j],dp[j-box[i]] + box[i]); } } printf("%d",v-dp[v]); return 0; } E. 买菜做饭Description
为了做饭，出题人拿了 k 块钱，准备去买食材。出题人准备买一只螃蟹和若干蔬菜。菜场里有 n 只螃蟹，第 i只螃蟹的价格为 c_i，美味值为 v_i，菜场里有 m 个蔬菜，第 i 个蔬菜的价格为 w_i，美味值为 p_i，求出题人的钱能换来最大的美味值。
Input
第一行三个正整数 k,n,m，
接下来 n 行，每行两个正整数 c_i,v_i，
接下来 m 行，每行两个正整数 w_i,p_i，
相邻整数均以空格分开
Output
一行一个整数，表示出题人的钱能换来最大的美味值
Sample input
23 2 2
2 3
3 4
10 10
10 10
Sample output
24
Note
all the numbers <= 3000
Time and memory limit
1s ，512M
#include<bits/stdc++.h> using namespace std; int w[3010],v[3010],c[3010]; int p[3010],dp[3010]; int main(){ int k,m,n; cin>>k>>n>>m; for(int i=1;i<=n;i++){ cin>>c[i]>>v[i]; } for(int i=1;i<=m;i++){ cin>>w[i]>>p[i]; } for(int i=1;i<=m;i++) { for(int j=k;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+p[i]); } } int ans=0; for(int i=1;i<=n;i++) { for(int j=c[i];j<=k;j++) { ans=max(ans,dp[j-c[i]]+v[i]); } } printf("%d\n",ans); return 0; } F. 美丽手镯时间：0.2s 空间：32M
题目描述：
有N个美丽的手镯，每个手镯有一个重量与美丽值，现在只能拿走最重总和不超过M的手镯，求最大的美丽值之和
输入格式：
第一行输入两个整数N,M
第二行到第N+1行每行输入两个整数Wi,Di,表示重量与美丽值
输出格式：
输出一个整数
样例输入：
4 6
1 4
2 6
3 12
2 7
样例输出：
23
约定：
1<=N<=3402,1<=M<=12880,1<=Wi<=400,1<=Di<=100
#include <bits/stdc++.h> using namespace std; const int maxn=3500,maxw=13000; int n,m; int w[maxn],v[maxn],dp[maxw]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&w[i],&v[i]); } for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } printf("%d\n",dp[m]); return 0; } G. 竞赛真理TENSHI在经历了无数次学科竞赛的失败以后，得到了一个真理：做一题就要对一题！但是要完全正确地做对一题是要花很多时间（包括调试时间），而竞赛的时间有限。所以开始做题之前最好先认真审题，估计一下每一题如果要完全正确地做出来所需要的时间，然后选择一些有把握的题目先做。 当然，如果做完了预先选择的题目之后还有时间，但是这些时间又不足以完全解决一道题目，应该把其他的题目用贪心之类的算法随便做做，争取“骗”一点分数。
输入格式：
第一行有两个正整数N和T，表示题目的总数以及竞赛的时限（单位秒）。以下的N行，每行４个正整数W1i 、T1i 、W2i 、T2i ，分别表示第i题：完全正确做出来的得分，完全正确做出来所花费的时间（单位秒），“骗”来的分数，“骗”分所花费的时间（单位秒）。
输出格式：
根据每一题解题时间的估计值，确定一种做题方案（即哪些题目认真做，哪些题目“骗”分，哪些不做），使能在限定的时间内获得最高的得分，
样例输入：
4 10800
18 3600 3 1800
22 4000 12 3000
28 6000 0 3000
32 8000 24 6000
样例输出：
50
数据范围：
3≤N≤30，2≤T≤1080000，1≤ W1i 、W2i ≤30000，1≤T1i 、T2i≤T
时间限制：
1000
空间限制：
65536
#include<bits/stdc++.h> using namespace std; const int MAXN = 1080010; int n , T; int w1[MAXN],t1[MAXN],w2[MAXN],t2[MAXN]; int dp[MAXN]; int solve(){ memset(dp , 0 , sizeof(dp)); int ans = 0; for(int i = 1 ; i <= n ; i++){ for(int j = T ; j >= 0 ; j--){ int tmp = dp[j]; if(j >= t1[i]) tmp = max(tmp , dp[j-t1[i]]+w1[i]); if(j >= t2[i]) tmp = max(tmp , dp[j-t2[i]]+w2[i]); dp[j] = max(dp[j] , tmp); ans = max(dp[j] , ans); } } return ans; } int main(){ scanf("%d%d" , &n , &T); for(int i = 1 ; i <= n ; i++) scanf("%d%d%d%d" , &w1[i] , &t1[i] , &w2[i] , &t2[i]); printf("%d\n" , solve()); return 0; } H. noip2006普及组 2.开心的金明（选做）时间：1s 空间：256M
题目描述：
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
输入格式：
第一行，两个整数，用空格分隔，N，m（N（<30000）表示总金额，m（<25）表示所需的项目。）
从第二行到第m + 1行，第j行给出了编号为j-1的项目的基本数据，每行有2个非负整数v和w（其中v是项目的价格（v <= 10000），w是项目的重要性（1~5））
输出格式：
一个整数，即产品价格和项目重要性的最大总和，而不是总金额（<100000000）。
样例输入：
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出：
3900
时限：
1S
题目描述
一个劫匪要去抢劫n家银行，每家银行有一定的现金，每抢一家银行该劫匪有一定几率被警察抓住，但是当该劫匪被抓住的几率小于p时他可以逃脱，问该劫匪在不被捕的情况下最多能抢到多少钱？
输入格式
第一行为用例组数T，每组用例第一行为一个浮点数P和一个整数n分别表示被捕的几率上限以及该劫匪计划抢劫的银行数量，之后n行每个一个整数M和一个浮点数p表示该家银行的现金数以及该劫匪抢劫该家银行被捕的几率
0<T≤100
0.0≤P≤1.0
0<n≤100
0≤Mj≤100
0.0≤pj≤1.0
输出格式
对于每组用例，输出该劫匪在不被捕的情况最多能抢到多少钱
样例输入
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
样例输出
2
4
6
时空限制
1s，512M
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int msz = 10000; const int mod = 1e9+7; const double eps = 1e-8; double dp[11234],pp[233]; int val[233]; int main(){ int t; double p; int n; scanf("%d",&t); for(int z = 1; z <= t; ++z){ scanf("%lf%d",&p,&n); int mx = 10000; for(int i = 0; i <= mx; ++i) dp[i] = -1; dp[0] = 0; for(int i = 0; i < n; ++i){ scanf("%d%lf",&val[i],&pp[i]); for(int j = mx; j >= val[i]; --j) { if(dp[j-val[i]] != -1) { if(dp[j] == -1) dp[j] = dp[j-val[i]]*(1-pp[i])+pp[i]; else dp[j] = min(dp[j],dp[j-val[i]]*(1-pp[i])+pp[i]); } } } for(int i = mx; i >= 0; --i) { if(dp[i] != -1 && dp[i] < p) { printf("%d\n",i); break; } } } return 0; } J. 大盗阿福(选做）描述
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
【输入】
输入的第一行是一个整数 T (T <= 50) ，表示一共有 T 组数据。
接下来的每组数据，第一行是一个整数 N (1 <= N <= 100, 000) ，表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。
【输出】
对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
样例输入
2
3
1 8 2
4 10 7 6 14
样例输出
8
24
提示
对于第一组样例，阿福选择第 2 家店铺行窃，获得的现金数量为 8 。
对于第二组样例，阿福选择第 1 和 4 家店铺行窃，获得的现金数量为 10 + 14 = 24 。
