5051 [JL] SJN的礼物
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 黄金 Gold
题目描述 Description
SJN因为被誉为逼神，于是SJN现在拿到了许多的礼物，他要把这些礼物放进袋子里。他很穷，只有一个最多装下V 体积物品的袋子，他不能全部放进去。他也拿不动那么重的东西。他估计他能拿的最大重量为 G。现在你了解了每一个物品的完美值、重量和体积，你当然想让SJN袋子中装的物品的完美值总和最大，你又得计划一下了。
输入描述 Input Description
第一行：G 和 V 表示最大重量和体积。第二行：N 表示拿到 N 件礼物。第三到N+2行：每行3个数 Ti Gi Vi 表示各礼物的完美值、重量和体积
输出描述 Output Description
输出共一个数，表示可能获得的最大完美值。
样例输入 Sample Input
6 5 4 10 2 2 20 3 240 4 330 3 3
样例输出 Sample Output
50
数据范围及提示 Data Size & Hint
对于20%的数据 N，V，G，Ti，Vi，Gi≤10
对于50%的数据 N，V，G，Ti，Vi，Gi≤100对于80%的数据 N，V，G，Ti，Vi，Gi≤30080%到100%的数据是N，V，G，Ti，Vi，Gi≤380 的离散随机数据。分类标签 Tags
#include#include using namespace std;const int N=1e3+10;int n,m,q,t[N],g[N],v[N],f[N][N];int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=q;i++) scanf("%d%d%d",t+i,g+i,v+i); for(int i=1;i<=q;i++){ for(int j=n;j>=g[i];j--){ for(int k=m;k>=v[i];k--){ f[j][k]=max(f[j][k],f[j-g[i]][k-v[i]]+t[i]); } } } printf("%d",f[n][m]); return 0;}
2564 Bone Collector骨骼收集家
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
题目描述 Description
许多年前，在泰迪镇有这么一个骨骼收集家。 这个人喜欢收集一些骨骼，比如：狗的、牛的、当然也有人骨…… 在他旅途中，他会带上一个体积V的大包，专门用来放置各种收集到的骨骼。 众所周知，不同的骨骼有着不同的收集价值和体积，这一点在其旅途中我们预先给出。 请你计算出骨骼收集家利用他的包，旅途中收集到的最大总价值？
输入描述 Input Description
第1行包含1个整数T，表示测试数据的组数。
1行包含两个整数V，N, (V <= 1000 , N <= 1000 )，其中：N表示骨骼的数量，V表示包的体积。
第2行包含N个整数，依次代表N个骨骼每一个骨骼的体积。
第3行包含N个整数，依次代表N个骨骼每一个骨骼的价值。 输出描述 Output Description
输出一个整数，占一行，表示总价值。（<2^31）
样例输入 Sample Input
110 51 2 3 4 55 4 3 2 1
样例输出 Sample Output
14
数据范围及提示 Data Size & Hint
总价值<2^31
骨骼的数量<= 1000
包的体积 <= 1000
分类标签 Tags
#includeusing namespace std;const int N=1e4+10;int n,m,T,v[N],c[N],f[N];int main(){ scanf("%d",&T); while(T--){ memset(f,0,sizeof f); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d",v+i); for(int i=1;i<=n;i++) scanf("%d",c+i); for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+c[i]); } } printf("%d\n",f[m]); } return 0;}
2042 顺序的分数
USACO
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。
这有一个例子，当N=5时，所有解为：
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
给定一个自然数N，1<=n<=160，请编程按分数值递增的顺序输出所有解。
注：①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。
输入描述 Input Description
单独的一行 一个自然数N(1..160)
输出描述 Output Description
每个分数单独占一行，按照大小次序排列
样例输入 Sample Input
5
样例输出 Sample Output
0/11/51/41/32/51/23/52/33/44/51/1
数据范围及提示 Data Size & Hint
见描述