| ||||||||||
| 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 | |||||||||
终于AC了,囧rz................#include<stdio.h>
#define wds -9999999
int f[120005];
int V;
int max(int x,int y){return x>y?x:y;}
void ZeroOnePack(int cost,int weight)
{
int v;
for(v=V;v>=cost;v--)
f[v]=max(f[v],f[v-cost]+weight);
}
void CompletePack(int cost,int weight)
{
int v;
for(v=cost;v<=V;v++)
f[v]=max(f[v],f[v-cost]+weight);
}
void MultiplePack(int cost,int weight,int mount)
{
if(cost*mount>=V)
{
CompletePack(cost,weight);
return;
}
int k=1;
while(k<mount)
{
ZeroOnePack(k*cost,k*weight);
mount-=k;
k=k*2;
}
ZeroOnePack(mount*cost,mount*weight);
}
int main()
{
// freopen("in.txt","r",stdin);
int n[7],i;
int num=0;
while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6]))
{
V=0;
for(i=1;i<=6;i++) V+=i*n[i];
if(V==0) break;
num++;
if(V%2!=0)
{
printf("Collection #%d:\n",num);
printf("Can't be divided.\n\n");
continue;
}
V=V/2;
f[0]=0;
for(int ii=1;ii<=V;ii++)
f[ii]=wds;
// else
{
for(i=1;i<=6;i++)
{
MultiplePack(i,i,n[i]);
}
// f[1],f[2],f[3],f[4],f[5],f[6];
if(V==f[V])
{
printf("Collection #%d:\n",num);
printf("Can be divided.\n\n");
}
else
{
printf("Collection #%d:\n",num);
printf("Can't be divided.\n\n");
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator