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

这题好诡异!

Posted by lianzhouxiaowu at 2010-03-15 14:23:48 on Problem 2581
/**********************************************
  二进制划分 
  下面是我0msAC的代码。但是
  在下面这个网站:http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2048 却一直WA!!!!!难道poj这里的数据弱??
**********************************************/
#include <stdio.h>
#include <algorithm>
#include <limits>
using namespace std;
const int inf = INT_MAX;
struct ma{
	int num[4];
	int all;
	ma operator=(ma mm){
		for(int i = 0; i < 4; i++) this->num[i] = mm.num[i];
		this->all = mm.all;
		return *this;
	}
}mas[1000];
struct com{
	int v;
	int k, num;
	void set(int v, int k, int num){
		this->v = v;
		this->k = k;
		this->num = num;
	}
}val[1000];
int cnt;
const int dig[4] = {25, 10, 5, 1}; 
int num[4];
int main(){
	int a, i;
	double tmp;
	for(i = 0; i < 4; i++) 
	while(scanf("%lf", &tmp) != EOF){
		a = tmp * 100;
		for(i = 0; i < 4; i++) scanf("%d", &num[i]);
		//二进制划分转化为单重背包问题
		cnt = 0;
		for(i = 0; i < 4; i++){
			int j = num[i];
			int k = 1;
			while(j > 0){
				if(j > k){
					j -= k;
					val[cnt].set(k * dig[i], i, k);
					cnt++;
				}else{
					val[cnt].set(j * dig[i], i, j);
					cnt++;
					j = 0;
				}
				k *= 2;
			}
		}
		//for(i = 0; i < cnt; i++) printf("dig[%d] = %d\n", i, val[i]);
		int j, k, sum = 0;
		for(i = 0; i <= a; i++){
			for(k = 0; k < 4; k++) mas[i].num[k] = 0;
			mas[i].all = inf;
		}
		mas[0].all = 0;
		for(i = 0; i < cnt; i++){ //printf("sum: %d\n", sum);
			for(k = sum; k >= 0; k--){
				int tmp = k + val[i].v;
				if(tmp <= a){
					if(mas[k].all != inf && mas[k].all + val[i].num < mas[tmp].all){
						//mas[k + val[i].v].all = mas[i].all + val[i].num;
						mas[tmp] = mas[k];
						mas[tmp].all += val[i].num;
						mas[tmp].num[val[i].k] += val[i].num;
						
					}
				}
			}
			sum += val[i].v;
			if(sum > a) sum = a;
		}
		
		/* 
		for(i = 0; i <= a; i++){ printf("val: %d  ", i);
			printf(" num: %d\n", mas[i].all);
			if(mas[i].all != inf){
				for(int j = 0; j < 4; j++) printf("%d ", mas[i].num[j]);
				printf("\n");
			}
		}
		*/ 
		

		if(mas[a].all == inf) printf("NO EXACT CHANGE\n");
		else{
			for(i = 0; i < 3; i++) printf("%d ", mas[a].num[i]);
			printf("%d\n", mas[a].num[3]);
		}
	}
	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