| ||||||||||
| 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 | |||||||||
Re:这题`DP 应该怎么写啊,我写的DP怎么超时了In Reply To:这题`DP 应该怎么写啊,我写的DP怎么超时了 Posted by:wincat at 2007-07-30 17:23:48 我也是啊。超时
#include<iostream>
void print(int id,int isOK){
if(isOK==1)
printf("Collection #%d:\nCan be divided.\n\n",id);
else printf("Collection #%d:\nCan't be divided.\n\n",id);
}
int main(){
int sum,i,j,k,a[7],time,temp;
char f[7][10001];
sum=0;
memset(a,0,sizeof(a));
for(i=1;i<=6;i++){
scanf("%d",&a[i]);
sum+=i*a[i];
}
time=1;
while(sum>0){
if(sum&1) print(time,0);
else {
sum=sum/2;
memset(f,0,sizeof(f));
for(i=0;i<=6;i++) f[i][0]=1;
for(i=1;i<=6;i++)
for(j=1;j<=sum;j++)
if(f[i-1][j]==1) f[i][j]=1;
else for(k=1;k<=a[i];k++)
if(f[i-1][j-k*i]==1&&j-i*k>=0)
f[i][j]=1;
temp=0;
for(i=1;i<=6;i++)
if(f[i][sum]==1){
temp=1;
break;
}
print(time,temp);
}
sum=0;
memset(a,0,sizeof(a));
for(i=1;i<=6;i++){
scanf("%d",&a[i]);
sum+=i*a[i];
}
time++;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator