| ||||||||||
| 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