HDU 1069 Monkey and Banana

Monkey and Banana

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;
}