Onway

pku 2392 Space Elevator 多重背包

 其实这个题找到了切入口后，是挺简单的。我似乎总有一种先入为主的倾向，想到一点点就下手，结果浪费时间，还掉入死胡同里。总之我是没找到那个切入口，然后看了一下discuss，原来排序就可以了，ft！！怎么我就笨得想不到了。其实我是想过排序，但没有深入去考虑。

 整个题最后的解肯定是不大于最大高度的type的。

将最大高度排序后，先叠好高度低的，高度大的叠在上面。

每一高度只要能组合就行进标记，不再浪费后面的blocks。同时对于某一blocks，只要枚举高度到该type的最大高度即可，并记录改高度使用了该type的blocks的个数。（背包部分）

 1#include <iostream>
 2#include <algorithm>
 3using namespace std;
 4const int MAX=40000;
 5const int MMAX=400;
 6struct type
 7{
 8    int h,a,c;
 9}data[MMAX+1];
10bool cmp(type x,type y)
11{
12    return x.a<y.a;
13}
14int cnt[MAX+1];
15bool sgn[MAX+1];
16int main()
17{
18    int n,i,j;
19    scanf("%d",&n);
20    for(i=1;i<=n;++i)    scanf("%d%d%d",&data[i].h,&data[i].a,&data[i].c);
21    sort(data+1,data+1+n,cmp);
22
23    memset(sgn,0,sizeof(sgn));
24    sgn[0]=1;
25    for(i=1;i<=n;++i)
26    {
27        memset(cnt,0,sizeof(cnt));
28        for(j=data[i].h;j<=data[i].a;++j)
29            if(!sgn[j]&&sgn[j-data[i].h]&&cnt[j-data[i].h]<data[i].c)
30            {
31                sgn[j]=1;
32                cnt[j]=cnt[j-data[i].h]+1;
33            }
34    }
35
36    for(j=data[n].a;j>=0;--j)
37        if(sgn[j])
38
39            break;
40    printf("%d\n",j);
41    return 0;
42}