hdu1881(贪心+dp)

时间:2024-10-13 13:34:38

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1881

分析:按照结束时间从小到大排序,然后以每个结束点为容量进行01背包,选入的必定符合条件的。

因为可能在某一结束点得到的价值最大,并不是dp[mx]最大容量得到的价值最大,所以要对dp值全部扫一遍得出最大值。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 10010
using namespace std;
struct node
{
int w,p,q;
bool operator<(const node &a)const
{
return q<a.q;
}
}s[];
int dp[];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int n;
while(scanf("%d",&n)>)
{
if(n<)break;
int v=;
for(int i=;i<=n;i++)
scanf("%d%d%d",&s[i].p,&s[i].w,&s[i].q),v=max(v,s[i].q);
sort(s+,s+n+);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++)
for(int j=s[i].q;j>=s[i].w;j--)
dp[j]=max(dp[j],dp[j-s[i].w]+s[i].p);
int mx=-;
for(int i=;i<=v;i++)mx=max(mx,dp[i]);
printf("%d\n",mx);
}
}