P1086 （C++代码）

解题思路:





注意事项:





参考代码:

#include<cstdio>  
#include<algorithm>  
using namespace std;  
inline int read()  
{  
    int x=0,f=1;char ch=getchar();  
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}  
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}  
    return x*f;  
}  
int n;  
struct structure{  
    int h,c,a;  
}dat[4001];  
inline bool cmp(const structure &a,const structure &b)  
{  
    if (a.a<b.a) return 1;  
    else if (a.a==b.a)  
    {  
        if (a.h<b.h) return 1;  
        else if (a.h==b.h)  
        {  
            if (a.c<b.c) return 1;  
            else return 0;  
        }else return 0;  
    }else return 0;  
}  
bool f[40010];  
int main()  
{  
    n=read();  
    for (int i=1;i<=n;i++)  
      dat[i].h=read(),dat[i].a=read(),dat[i].c=read();  
    sort(dat+1,dat+1+n,cmp);  
    f[0]=1;  
    for (int i=1;i<=n;i++)  
      for (int j=1;j<=dat[i].c;j++)  
        for (int k=dat[i].a;k>=dat[i].h;k--)  
          f[k]|=f[k-dat[i].h];  
    for (int i=40005;i>=0;i--)  
      if (f[i])  
      {  
        printf("%d",i);  
        return 0;  
      }  
}