Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

0/1背包解法

Posted by meJustPlay at 2012-05-01 02:10:19 on Problem 2392
/** 
 * 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator