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 |
这题好诡异!/********************************************** 二进制划分 下面是我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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator