POJ 2392 DP

题目链接:http://poj.org/problem?id=2392

有一头牛想要建一座石塔,他有很多不同类型的石块。
每类石块有三个属性:

  1. $h_i$: 石块的高度
  2. $a_i$: 石块能放的最大高度(石头的任意一部分的高度都不能超过 $a_i$)
  3. $c_i$: 石块的数量

问能建的塔的最大高度。

思路

将所有石块按照 $a_i$ 排序,因为 $a_i$ 的石块必须提前考虑,才能覆盖全部解空间。

定义 $dp[i][j]$ 为用前 $i$ 种石块搭建高度为 $j$ 的塔时,第 $i$ 种石块最多剩余多少个。

显然如果 $dp[i - 1][j] \geq 0$,$dp[i][j] = c_i$(第 $i$ 种石块则可以剩余 $c_i$ 个);而如果 $j > a_i$,则 $dp[i][j] = -1$(塔不可能达到这个高度);正常情况则 $dp[i][j] = dp[i][j - h_i] - 1$。

2392.cppview raw
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define maxn 405
#define maxa 40050
using namespace std;

struct block {
int h, a, c;
}b[maxn];

int dp[maxn][maxa];

bool cmp(const block& x, const block& y) {
return x.a < y.a;
}


int main() {
int n; cin >> n;
for (int i = 0; i < n; i++)
scanf("%d %d %d", &b[i].h, &b[i].a, &b[i].c);

sort(b, b + n, cmp);

memset(dp, -1, sizeof dp);
for (int i = 0; i < n; i++)
dp[i][0] = b[i].c;
for (int i = 0; i < n; i++)
for (int j = 1; j <= b[i].a; j++)
if (i && dp[i - 1][j] >= 0)
dp[i][j] = b[i].c;
else if (j - b[i].h >= 0)
dp[i][j] = dp[i][j - b[i].h] - 1;

int ans = 0;
for (int j = 0; j < maxa; j++)
if (dp[n - 1][j] >= 0)
ans = j;
cout << ans << endl;
return 0;
}