HDU - 3127

 

传送门

 

有一个X*Y的大矩形，有N种小矩形，每种两条边为x[i],y[i],价值val[i]（旋转90度，价值不变）;每次操作允许你将矩形平行着边将矩形切割成两个小的矩形，求你能切割多次切割原来的大矩形能获得的最大价值。

定义dp[i][j]为大小为i*j的矩形能获得的最大价值。对于每个i*j矩形，我们枚举每个小矩形，将小矩形的放在大矩形的左上角，分别沿着小矩形的某条边进行切割，然后再切割得到小矩形，这时把原有的大矩形切割成小矩形和另外两个矩形。将小矩形旋转90度，再进行上述操作即可。

 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
typedef long long LL;

const int maxn = 1e3 + 10;
int T;
int N;
int X, Y;
int val[maxn], x[maxn], y[maxn];
int dp[maxn][maxn];

int main(int argc, const char * argv[]) {
    scanf("%d", &T);
    while (T--) {
        memset(dp, 0, sizeof(dp));
        scanf("%d%d%d", &N, &X, &Y);
        for (int i = 0; i < N; i++) {
            scanf("%d%d%d", &x[i], &y[i], &val[i]);
        }
        for (int i = 0; i <= X; i++) {
            for (int j = 0; j <= Y; j++) {
                for (int k = 0; k < N; k++) {
                    int a = x[k], b = y[k];
                    if (i >= a && j >= b) {
                        dp[i][j] = max(dp[i][j],
                                   max(dp[a][j - b] + dp[i - a][j], dp[i - a][b] + dp[i][j - b]) + val[k]);
                    }
                    if (j >= a && i >= b) {
                        dp[i][j] = max(dp[i][j],
                                   max(dp[b][j - a] + dp[i - b][j], dp[i - b][a] + dp[i][j - a]) + val[k]);
                    }
                }
            }
        }
        printf("%d\n", dp[X][Y]);
    }
    return 0;
}