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

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

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define INF 0x3f3f3f3f 6 #define MOD 1000000007 7 using namespace std; 8 typedef long long LL; 9 10 const int maxn = 1e3 + 10;11 int T;12 int N;13 int X, Y;14 int val[maxn], x[maxn], y[maxn];15 int dp[maxn][maxn];16 17 int main(int argc, const char * argv[]) {18     scanf("%d", &T);19     while (T--) {20         memset(dp, 0, sizeof(dp));21         scanf("%d%d%d", &N, &X, &Y);22         for (int i = 0; i < N; i++) {23             scanf("%d%d%d", &x[i], &y[i], &val[i]);24         }25         for (int i = 0; i <= X; i++) {26             for (int j = 0; j <= Y; j++) {27                 for (int k = 0; k < N; k++) {28                     int a = x[k], b = y[k];29                     if (i >= a && j >= b) {30                         dp[i][j] = max(dp[i][j],31                                    max(dp[a][j - b] + dp[i - a][j], dp[i - a][b] + dp[i][j - b]) + val[k]);32                     }33                     if (j >= a && i >= b) {34                         dp[i][j] = max(dp[i][j],35                                    max(dp[b][j - a] + dp[i - b][j], dp[i - b][a] + dp[i][j - a]) + val[k]);36                     }37                 }38             }39         }40         printf("%d\n", dp[X][Y]);41     }42     return 0;43 }