| ||||||||||
| 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 | |||||||||
多重背包+dp (附代码)#include "stdio.h"
#include "memory.h"
int result [3][10000*6+1];
int main(void)
{
int i,sum=0,con=0,j,l,flag=0,temp,k,count[2],front,last;
int a[6];
while(++con)
{
flag=0;
sum=0;
for(i=0;i!=6;++i)
{
scanf("%d",a+i);
if(a[i]!=0) flag=1;
sum+=a[i]*(i+1);
}
if(flag==0) return 0;
if(sum%2==1) { printf("Collection #%d:\nCan't be divided.\n\n",con);continue;}
sum/=2;
memset(result[2],0,sizeof(int)*60001);
result[2][0]=1;
result[0][0]=0;
front=1;last=0;
count[0]=1;
count[1]=0;
for(i=6;i!=0;--i)
{
for(j=a[i-1];j>0;--j)
{
if(front==1){front=0;last=1;}
else {front=1;last=0;}
count[last]=0;
for(k=count[front]-1;k>=0;--k)
{
temp=result[front][k]+i;
if(temp==sum) {result[2][sum]=1; goto lo;}
if(temp<sum&&result[2][temp]!=1)
{
result[2][temp]=1;
result[last][count[last]++]=temp;
}
}
}
count[last]=0;
for(j=0;j<=sum;++j)
{
if(result[2][j])
result[last][count[last]++]=j;
}
}
lo: if(result[2][sum]==1)
printf("Collection #%d:\nCan be divided.\n\n",con);
else printf("Collection #%d:\nCan't be divided.\n\n",con);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator