事务所网站制作方案,集团公司网站建设品牌,凡科建站网站,装修门户网站程序 cms题意#xff1a; 有 n 个池塘#xff0c;只能从第一个池塘开始走#xff0c;可以在每个池塘中钓鱼#xff0c;而且知道了每个池塘每五分钟钓鱼的数量都会下降一定额数值#xff0c;且从池塘到下一个池塘之间都有一定的距离#xff0c;知道了每个池塘走到下一个池塘的时间…题意 有 n 个池塘只能从第一个池塘开始走可以在每个池塘中钓鱼而且知道了每个池塘每五分钟钓鱼的数量都会下降一定额数值且从池塘到下一个池塘之间都有一定的距离知道了每个池塘走到下一个池塘的时间和每个池塘一开始能够钓鱼的数量求在规定的时间内所能钓的最多的鱼的数量。 分析 枚举以每个池塘为终点的情况找到最大值。 有个注意的地方就是没枚举一个终点先把这段路的每个间隔所花时间去掉这样就可以每次贪心去找单位时间可以钓最多的鱼了而且可以保证贪心到最后可以找到最优解。 #includecstdio
#includecstring
#define clr(x)memset(x,0,sizeof(x))
struct node
{int f; // 开头 5 分钟钓的鱼数量 int d; // 每五分钟减少的数量int dis; // 到下一个池塘的时间
}l[202];
int a[202]; // 保存每个池塘一开始可以钓的鱼
int tim[202][2500];
int res[202];
int main()
{int n,i,j,k,t,tot,tt,max;while(scanf(%d,n),n){clr(a);clr(tim);clr(res);scanf(%d,t);tott*12;for(i0;in;i)scanf(%d,l[i].f);for(i0;in;i)scanf(%d,l[i].d);for(i0;in-1;i)scanf(%d,l[i].dis);for(i0;in;i){ttot;for(j0;ji;j)t-l[j].dis;for(j0;ji;j)a[j]l[j].f;for(j0;jt;j){maxa[0];tt0;for(k0;ki;k)if(a[k]max){maxa[k];ttk;}a[tt]-l[tt].d;res[i]max;if(a[tt]0)a[tt]0;tim[i][tt];}}maxres[0];tt0;for(i1;in;i)if(res[i]max){maxres[i];tti;}for(i0;in-1;i)printf(%d, ,tim[tt][i]*5);printf(%d\n,tim[tt][i]*5);printf(Number of fish expected: %d\n\n,max);}return 0;
} 转载于:https://www.cnblogs.com/dream-wind/archive/2012/07/27/2612598.html
