| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
0/1背包解法/** * POJ: 2392 Space Elevator * * DP: Multiple Pack + 排序 * K种Block(Bi: 高度Hi, 数量Ci, 不能超过高度Ai); 求可以达到的最大高度; */ /** ***/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> /** ***/ #define CNT 1600 // K <= 400, Ci <= 10 #define SIZ 40000 // Ai <= 40000 /** ***/ typedef struct { int h; // hi int a; // ai int c; // ci } blk_t; blk_t blk[CNT + 1]; // 0/1 pack int dp[SIZ + 1]; // dp[i][j]: 考察前i种block, 容量为j的背包的最大值 /** ***/ static inline int max(int a, int b) { return (a > b ? a : b); } /** ***/ int compar(const void *a, const void *b) { blk_t *aa = (blk_t *)a; blk_t *bb = (blk_t *)b; if (aa->a != bb->a) { return aa->a - bb->a; } else { return aa->h - bb->h; } } /** ***/ int main(int argc, char **argv) { #ifndef SUBMIT // freopen("input/2392", "r", stdin); #endif int cnt, hgt, ans; int kid, hi, ai, ci; while (1 == scanf("%d", &kid)) { /* init */ cnt = hgt = ans = 0; memset(dp, 0, sizeof(dp)); /* input && convert*/ for (int i = 0; i < kid; ++i) { scanf("%d%d%d", &hi, &ai, &ci); hgt = max(hgt, ai); for (int j = 1; j < ci; j <<= 1) { if (j * hi > ai) { // hi > ai时, 丢弃之 continue; } blk[++cnt].h = j * hi; blk[cnt].a = ai; ci -= j; } if (ci * hi > ai) { continue; } blk[++cnt].h = ci * hi; blk[cnt].a = ai; } /* resolve */ qsort(blk + 1, cnt, sizeof(blk_t), compar); for (int i = 1, tmp = 0; i <= cnt; ++i) { for (int j = hgt; j >= blk[i].h; --j) { tmp = dp[j - blk[i].h] + blk[i].h; if (tmp <= blk[i].a) { dp[j] = max(dp[j], tmp); ans = max(ans, dp[j]); } } } /* output */ printf("%d\n", ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator