本文主要是介绍ycb的ACM进阶之路（背包优化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
ycb的ACM进阶之路
发布时间: 2017年5月22日 14:30 最后更新: 2017年5月22日 14:31 时间限制: 1000ms 内存限制: 128M
ycb是个天资聪颖的孩子，他的梦想是成为世界上最伟大的ACMer。为此，他想拜附近最有威望的dalao为师。dalao为了判断他的资质，给他出了一个难题。dalao把他带到一个到处都是题的oj里对他说：“孩子，这个oj里有一些不同的题，做每一道题都需要一些时间，每一题也有它自身的rp（人品值）。我会给你一段时间，在这段时间里，你可以做一些题。如果你是一个聪明的孩子，你应该可以让做题的总rp最大。” 如果你是ycb，你能完成这个任务吗？
输入文件的第一行是一个T，表示测试组数，接下来T组每组第一行包含两个正整数N,M。M表示总共能够用来做题的时间，N代表oj里的题目的数目。接下来的N行每行包括两个的整数，分别表示做每个题的时间Ti和这道题的人品值Vi。
1 <= N, M <= 100000,
1 <= Ti, Vi <= 10
输出文件仅包含一个整数表示规定时间内可以做题得到的最大人品值。
1 3 9 10 10 8 1 1 2
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
const int inf = -0x3f3f3f3f;
typedef pair <int , int> pp;
int dp[100005];
int tm[100055];
int rp[100005];
map <pp, int> mp;
int main()
{int t,m,T;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));mp.clear();scanf("%d%d",&m,&T);for(int i = 1; i <= m; i++){scanf("%d%d",&tm[i],&rp[i]);mp[make_pair(tm[i],rp[i])] ++;if(mp[make_pair(tm[i],rp[i])] >= 2)//找重复的元素，只保留一个并记录个数。{i--,m--;}}int j = m;for(int i = 1; i <= m; i++){int tt = tm[i];int rr = rp[i];int num = mp[make_pair(tt,rr)]-1;int k = 1;while(num>0){int tmp = min(num , 1<<k);num -= 1<<k++;tm[++j] = tt*tmp;rp[j] = rr*tmp;}}m = j;for(int i = 1; i <= m; i++)for(int j = T; j >= tm[i]; j--){dp[j] = max(dp[j],dp[j-tm[i]]+rp[i]);}printf("%d\n",dp[T]);}return 0;
}这篇关于ycb的ACM进阶之路（背包优化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
