【POJ2392】带有限制的多重背包

1.​​题目链接​​。题目大意：给你一堆Bolcks，每种Bolcks有三种属性：数量，高度，以及最高能放置的高度。问你用这些Bolcks能够组合堆起来最高的高度是多少。这个如果没有第三个条件，我们直接多重背包即可。第三个条件是什么意思呢？它就是在说，这些砖块所能放置的高度是有区间限制的。在这种情况下，求组合起来的最大值。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#pragma warning(disable:4996)
const int N = 4e4 + 10;
struct Block
{
  int a, h, c;
}b[410];
bool cmp(Block x, Block y)
{
  return x.a < y.a;
}
int dp[N], use[N];
int main()
{
  int T;
  scanf("%d", &T);
  for (int i = 0; i < T; i++)
  {
    scanf("%d%d%d", &b[i].h, &b[i].a, &b[i].c);
  }
  sort(b, b + T,cmp);
  int ans = 0;
  dp[0] = 1;
  for (int i = 0; i < T; i++)
  {
    memset(use, 0, sizeof(use));
    for (int j = b[i].h; j <= b[i].a; j++)
    {
      if (!dp[j] && dp[j - b[i].h] && use[j-b[i].h] + 1 <= b[i].c)
      {
        dp[j] = 1;
        ans = max(ans, j);
        use[j] = use[j - b[i].h] + 1;
      }
    }
  }
  printf("%d\n", ans);
}