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);

    }

}

相关文章