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