[TIOJ 1675] 可能的任務

作法：

首先可以想到，如果有一個任務的報酬 <= 需要的錢，那麼就不要選這個任務，因為這樣可以讓最後的錢數增加和體力增加，會讓情況更好。看到 N , P <= 5000 大概可以知道是DP，但我們還不知道任務完成的順序，所以應該要先知道按照怎樣的順序完成任務會是最好的。可以發現花費越少的任務擺越前面越好，因為如果有兩個任務，後完成的花費比先完成的花費少，那直接把這兩個任務的位子交換不會讓情況更差，所以只要排序過後DP就好了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10 ;
 
struct P
{
    int c,add,p ;
    bool operator < (const P &rhs) const
    {
        return c==rhs.c ? add>rhs.add : c<rhs.c ;
    }
}a[maxn];
 
int dp[maxn] ;
main()
{
    int n,c,m ; scanf("%d%d%d",&n,&c,&m) ;
    int n2=0 ;
    for(int i=1;i<=n;i++)
    {
        int x,y,z ; scanf("%d%d%d",&x,&y,&z) ;
        if(y<=x) continue ;
        n2++ ;
        a[n2]=(P){x,y-x,z} ;
    }
    n=n2 ;
    sort(a+1,a+n2+1) ;
    for(int i=1;i<=m;i++) dp[i]=c ;
    for(int i=1;i<=n;i++) for(int j=m;j>a[i].p;j--)
        if(dp[j-a[i].p]>a[i].c)
            dp[j]=max(dp[j],dp[j-a[i].p]+a[i].add) ;
    printf("%d\n",dp[m]) ;
}