n<=400个东西,每个东西有高度<=100,这种东西在堆放过程中不得超过的最大高度<=40000,以及每个东西的个数<=10,求最高能堆多高。
算了下背包复杂度不太对然后开了bitset。。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<bitset>
//#include<iostream>
using namespace std; int n;
#define maxn 411
struct Obj{int h,m,c;}a[maxn];
bool cmp(const Obj &a,const Obj &b) {return a.m<b.m;}
bitset<> f,tmp,t;
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d%d%d",&a[i].h,&a[i].m,&a[i].c);
f.reset();f[]=;
tmp.set();
sort(a+,a++n,cmp);
for (int i=;i<=n;i++)
{
for (int j=;j<=a[i].c;j++)
f|=(f<<a[i].h);
t=tmp<<(a[i].m+);t.flip();
f&=t;
}
int ans;
for (ans=;ans;ans--) if (f[ans]) break;
printf("%d\n",ans);
return ;
}