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

Multiple && Complete Pack[转01; 可以不排序]

Posted by meJustPlay at 2012-05-05 01:17:46 on Problem 3260
/**
 * POJ: 3260 The Fewest Coins
 *
 * DP:  Multiple/Complete Pack
 *
 * 此道题的数据__弱__
 */

/** ***/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/** ***/
#define INP	100
#define KND	INP * 10

#define T	10000
#define SP	T + 10
#define FJ	SP 

#define SUBMIT	1

/** ***/
#define min(a, b) ( (a) < (b) ? (a) : (b) )
#define max(a, b) ( (a) > (b) ? (a) : (b) )

/** ***/
int knd;	// kinds of coins(N);
int cst;	// the total cost(T);

int fj[FJ + 1];	// fj[i]: FJ付款i所用的最小coins
int sp[SP + 1];	// sp[j]: SP找零j所用的最小coins

typedef struct {
	int val;
	int cnt;
} coin_t;
coin_t con[KND + 1];	// 0/1 Pack
coin_t inp[INP + 1];	// input 

/** ***/
int compar(const void *p1, const void *p2)
{
	/* descending order */
	return ((coin_t *)p2)->val - ((coin_t *)p1)->val;
}

/** ***/
int main(int argc, char **argv)
{
	#ifndef SUBMIT
	freopen("input/3260", "r", stdin);
	#endif

	int n;
	int ans;	// the result;
	int mny;	// the maximum coins we study

	while (2 == scanf("%d%d", &n, &cst)) {
		/* init */
		ans = INT_MAX;
		knd = mny = 0;
		memset(fj, 0, sizeof(fj));
		memset(sp, 0, sizeof(sp));

		/* input */
		for (int i = 0; i < n; ++i) {
			scanf("%d", &inp[i].val);
		}
		for (int i = 0; i < n; ++i) {
			scanf("%d", &inp[i].cnt);
		}

		/* convert */
		for (int i = 0; i < n; ++i) {
			if (!inp[i].cnt) {	// for CompletePack
				con[++knd].val = inp[i].val;
				con[knd].cnt   = 0;

				continue;
			}
			for (int k = 1; k < inp[i].cnt; k <<= 1) {
				con[++knd].val = inp[i].val * k;
				con[knd].cnt   = k; 
				inp[i].cnt -= k;
			}
			con[++knd].val = inp[i].val * inp[i].cnt;
			con[knd].cnt   = inp[i].cnt;
		}

		/* sort */
		qsort(con + 1, knd, sizeof(coin_t), compar);

		/* dp <-> fj */
		for (int i = 1, nt; i <= knd; ++i) {
			if (!con[i].cnt) {	// when (cnt = 0) skip;
				continue;
			}
			for (int j = mny; j >= 0; --j) {
				if (!fj[j] && j) {	// fj[0] === 0;
					continue;
				}

				nt = j + con[i].val;
				if (nt > T) {	/* !!! */
					continue;
				}

				if (!fj[nt]) {
					fj[nt] = fj[j] + con[i].cnt;
				} else {
					fj[nt] = min(fj[nt], fj[j] + con[i].cnt);
				}

				mny = max(mny, nt);
			}
		}

		/* little optimizations */
		/* !!! NOT fj[cst] !!! */
		if (mny < cst) {
			printf("-1\n");
			continue;
		}
		
		/* dp <-> sp */
		for (int i = 1, nt, ct; i <= knd; ++i) {
			if (!con[i].cnt) {
				con[i].cnt = 1;
			}

			for (int j = 1; j <= mny - cst; ++j) {
				for (int k = 1; ; ++k) {
					nt = con[i].val * k;
					ct = con[i].cnt * k;
					if (nt > j) {
						break;
					}

					// 求的是__j可以达到时候__的最小值
					if (!sp[j - nt] && (j ^ nt)) {
						continue;
					}
					
					if (!sp[j]) {
						sp[j] = sp[j - nt] + ct;
					} else {
						sp[j] = min(sp[j], sp[j - nt] + ct);
					}
				}
			}
		}

		/* resolve */
		if (fj[cst]) {
			ans = min(ans, fj[cst]);
		}
		for (int i = cst + 1; i <= mny; ++i) {
			if (fj[i] && sp[i - cst]) {
				ans = min(ans, fj[i] + sp[i - cst]);
			}
		}

		/* output */
		ans == INT_MAX ? printf("-1\n") : 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