poj2392 Space Elevator(多重背包)

xiaoxiao2021-02-28  86

n种砖头,每种砖头还有最高高度限制和数量限制。把所有砖头按最高高度从小到大排序,然后就可以直接多重背包了。

#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; #define N 401 int n,cnt[40010],ans=0; bool f[40010]; struct node{ int h,a,num; }a[N]; inline bool cmp(node x,node y){return x.a<y.a;} int main(){ // freopen("a.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i].h,&a[i].a,&a[i].num); sort(a+1,a+n+1,cmp);f[0]=1; for(int i=1;i<=n;++i){ memset(cnt,0,sizeof(cnt)); for(int j=a[i].h;j<=a[i].a;++j) if(!f[j]&&f[j-a[i].h]&&cnt[j-a[i].h]+1<=a[i].num){ f[j]=1;cnt[j]=cnt[j-a[i].h]+1; if(j>ans) ans=j; } } printf("%d\n",ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-63729.html

最新回复(0)