【Tyvj1086】Elevator

2014-05-25
竞赛题解 / 动态规划
TYVJ

描述 Description

现有 N 种箱子，每种箱子高度 H_i，数量 C_i。现选取若干箱子堆成一列，且第 i 种箱子不能放在高度超过 A_i 的地方。试求最大叠放高度。

输入格式 InputFormat

第一行，一个整数，表示箱子种类 N。
接下来 N 行，每行三个整数，表示 H_i，A_i，C_i。

输出格式 OutputFormat

一个整数，表示最大高度。

样例输入 SampleInput

10
51 1663 5
48 1223 7
56 82 9
11 1833 6
11 791 3
75 535 9
75 1775 5
49 921 9
63 715 3
60 87 6

样例输出 SampleOutput

1833

Tyvj 1086

代码 Code

水。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct box
{
    int h,c,s;
}a[401];
int i,j,t,n,m,l,r,k,z,y,x,ans;
bool f[100000];
bool comp(box a,box b)
{
    return a.s<b.s;
}
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d%d%d",&a[i].h,&a[i].s,&a[i].c);
    sort(a+1,a+n+1,comp);
    f[0]=true;
    ans=0;
    for (i=1;i<=n;i++) for (j=1;j<=a[i].c;j++) for (k=a[i].s;k>=a[i].h;k--)
    {
        if (f[k-a[i].h]) 
        {
            f[k]=true;
            ans=max(ans,k);
        }
    }
    printf("%d\n",ans);
    return 0;
}