国家重大建设项目网站地址,做网站公司起什么名字,开发公司补偿物业公司物业费协议,网页设计教案题干#xff1a;
ycb的ACM进阶之路
Description ycb是个天资聪颖的孩子#xff0c;他的梦想是成为世界上最伟大的ACMer。为此#xff0c;他想拜附近最有威望的dalao为师。dalao为了判断他的资质#xff0c;给他出了一个难题。dalao把他带到一个到处都是题的oj里对他说
ycb的ACM进阶之路
Description ycb是个天资聪颖的孩子他的梦想是成为世界上最伟大的ACMer。为此他想拜附近最有威望的dalao为师。dalao为了判断他的资质给他出了一个难题。dalao把他带到一个到处都是题的oj里对他说“孩子这个oj里有一些不同的题做每一道题都需要一些时间每一题也有它自身的rp人品值。我会给你一段时间在这段时间里你可以做一些题。如果你是一个聪明的孩子你应该可以让做题的总rp最大。” 如果你是ycb你能完成这个任务吗
Input
输入文件的第一行是一个T表示测试组数接下来T组每组第一行包含两个正整数N,M。M表示总共能够用来做题的时间N代表oj里的题目的数目。接下来的N行每行包括两个的整数分别表示做每个题的时间Ti和这道题的人品值Vi。 1 N, M 100000, 1 Ti, Vi 10
Output
输出文件仅包含一个整数表示规定时间内可以做题得到的最大人品值。
Sample Input 1
1
3 9
10 10
8 1
1 2
Sample Output 1
3
Hint
作者
青岛大学acm集训队1号命题组
Source
lalal
解题报告 这题好题啊0-1背包转化成多重背包来做因为v和w的数据量都很小 一共100种组合所以可以枚举然后转化成多重背包来做。
AC代码
#includebits/stdc.husing namespace std;
int n,m;
int ji[15][15];
int dp[1000000],w[1000000],v[1000000];
int main()
{int t;int time,rp;cint;while(t--) {scanf(%d%d,n,m);memset(ji,0,sizeof(ji));memset(dp,0,sizeof(dp));for(int i 1; in; i) {scanf(%d%d,time,rp);ji[time][rp];}int top 0;for(int i 1; i10; i) {for(int j 1; j10; j) {if(ji[i][j] 0) continue;for(int k 1; kji[i][j]; k1) {w[top] i * k;v[top] j * k;ji[i][j] - k;}if(ji[i][j]0) {w[top] ji[i][j] * i;v[top] ji[i][j] * j;} }}for(int i 1; itop; i) {for(int j m; jw[i]; j--) {dp[j] max(dp[j],dp[j - w[i] ] v[i]);} }printf(%d\n,dp[m]);}return 0 ;
}
