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}