dp[i][j][k]:堆i个箱子,最底下的箱子为第j个,且该箱子为第k个姿态(长x,宽y,高z的组合).
状态转移方程见代码.
其实可以把同一种箱子的不同姿态当作不同的箱子存进去,然后状态转移的时候直接比较x和y,状态转移那里就不用写那么繁琐了.
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;
int dp[91][35][3];
int a[35][3];
int t[35][3];
int main() {
int n, k = 0;
while (cin >> n && n) {
int ans = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
sort(a[i], a[i] + 3);
dp[1][i][0] = a[i][0];
dp[1][i][1] = a[i][1];
dp[1][i][2] = a[i][2];
ans = max(ans, dp[1][i][0]);
ans = max(ans, dp[1][i][1]);
ans = max(ans, dp[1][i][2]);
}
for (int i = 2; i <= n * 3; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
if (a[j][1] > a[k][1] && a[j][2] > a[k][2])
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][0] + a[j][0]);
if (a[j][1] > a[k][0] && a[j][2] > a[k][2])
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][1] + a[j][0]);
if (a[j][1] > a[k][0] && a[j][2] > a[k][1])
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][2] + a[j][0]);
if (a[j][0] > a[k][1] && a[j][2] > a[k][2])
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][0] + a[j][1]);
if (a[j][0] > a[k][0] && a[j][2] > a[k][2])
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][1] + a[j][1]);
if (a[j][0] > a[k][0] && a[j][2] > a[k][1])
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][2] + a[j][1]);
if (a[j][0] > a[k][1] && a[j][1] > a[k][2])
dp[i][j][2] = max(dp[i][j][2], dp[i - 1][k][0] + a[j][2]);
if (a[j][0] > a[k][0] && a[j][1] > a[k][2])
dp[i][j][2] = max(dp[i][j][2], dp[i - 1][k][1] + a[j][2]);
if (a[j][0] > a[k][0] && a[j][1] > a[k][1])
dp[i][j][2] = max(dp[i][j][2], dp[i - 1][k][2] + a[j][2]);
ans = max(ans, dp[i][j][0]);
ans = max(ans, dp[i][j][1]);
ans = max(ans, dp[i][j][2]);
}
}
}
printf("Case %d: maximum height = %d\n", ++k, ans);
}
return 0;
}