1 #include <stdio.h> 2 #include <string.h> 3 4 #define mymax(a, b) (a>b) ? a:b 5 6 typedef struct { 7 int x, y, c; 8 } rect_st; 9 10 rect_st rects[15]; 11 12 int dp[1005][1005]; 13 14 int main() { 15 int case_n; 16 int x, y, n; 17 int i, j, k, tmp; 18 19 scanf("%d", &case_n); 20 21 while (case_n--) { 22 scanf("%d%d%d", &n,&x,&y); 23 for (i=1; i<=n; ++i) 24 scanf("%d%d%d", &rects[i].x, &rects[i].y, &rects[i].c); 25 memset(dp, 0, sizeof(dp)); 26 for (i=1; i<=x; ++i) { 27 for (j=1; j<=y; ++j) { 28 for (k=1; k<=n; ++k) { 29 if (i>=rects[k].x && j>=rects[k].y) { 30 tmp = mymax(dp[i-rects[k].x][j]+dp[rects[k].x][j-rects[k].y], dp[i][j-rects[k].y]+dp[i-rects[k].x][rects[k].y]); 31 dp[i][j] = mymax(dp[i][j], tmp+rects[k].c); 32 } 33 if (i>=rects[k].y && j>=rects[k].x) { 34 tmp = mymax(dp[i-rects[k].y][j]+dp[rects[k].y][j-rects[k].x], dp[i][j-rects[k].x]+dp[i-rects[k].y][rects[k].x]); 35 dp[i][j] = mymax(dp[i][j], tmp+rects[k].c); 36 } 37 } 38 } 39 } 40 printf("%d ", dp[x][y]); 41 } 42 43 return 0; 44 }
完全背包。