| ||||||||||
| 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>
int d[51][301];
bool c[51][301];
int s[51][301];
int fi[51];
int di[51];
int ti[51];
int len,h;
int catchnum(int k,int lake)
{
if(fi[lake]==0) return 0;
if(di[lake]==0) return fi[lake]*k;
if(fi[lake]%di[lake]==0&&k>fi[lake]/di[lake])
return (fi[lake]+di[lake])*(fi[lake]/di[lake])/2;
if(fi[lake]%di[lake]!=0&&k>fi[lake]/di[lake])
return (fi[lake]+di[lake]+fi[lake]%di[lake])*(fi[lake]/di[lake])/2+fi[lake]%di[lake];
return (fi[lake]+fi[lake]-(k-1)*di[lake])*k/2;
}
void printans(int t)
{
for(int i=1;i<=len-1;i++)
{
printf("%d, ",s[i][t]*5);
if(t==0||t-s[i][t]-ti[i]<=0)
t=0;
else
t=t-s[i][t]-ti[i];
}
printf("%d\n",s[len][t]*5);
}
long dp(int lake,int t)
{
if(c[lake][t]==1)
return d[lake][t];
else
{
d[lake][t]=catchnum(t,lake);
s[lake][t]=t;
if(t-ti[lake]>0)
{
for(int k=t-ti[lake]-1;k>=0;k--)
{
int temp=catchnum(k,lake)+dp(lake+1,t-k-ti[lake]);
if(temp>d[lake][t])
{
d[lake][t]=temp;
s[lake][t]=k;
}
}
}
}
c[lake][t]=1;
return d[lake][t];
}
int main(void)
{
scanf("%d",&len);
while(len>0)
{
scanf("%d",&h);h*=12;
for(int i=1;i<=len;i++)
scanf("%d",&fi[i]);
for(int i=1;i<=len;i++)
scanf("%d",&di[i]);
for(int i=1;i<=len-1;i++)
scanf("%d",&ti[i]);
for(int i=1;i<=len;i++)
for(int j=1;j<=h;j++)
c[i][j]=0;
for(int i=1;i<=len;i++)
{
d[i][0]=0;c[i][0]=1;
s[i][0]=0;
}
for(int i=1;i<=h;i++)
{
d[len][i]=catchnum(i,len);
c[len][i]=1;
s[len][i]=i;
}
int ans=dp(1,h);
printans(h);
printf("Number of fish expected: %d\n\n",ans);
scanf("%d",&len);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator