1 #include2 #include 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\n", dp[x][y]);41 }42 43 return 0;44 }
完全背包。