题目描述

约翰是个垂钓谜，星期天他决定外出钓鱼h小时（1≤h≤16），约翰家附近共有n个池塘（2≤n≤25），这些池塘分布在一条直线上，约翰将这些池塘按离家的距离编上号，依次为L1,L2,…,Ln，他从湖1出发，向右走，有选择性地在一些湖停留一定的时间钓鱼，最后在某一个湖结束钓鱼。

约翰家门外就是第一个池塘，所以他到第一个池塘是不用花时间的，约翰可以任选若干个池塘垂钓，并且在每个池塘他都可以呆上任意长的时间，但呆的时间必须为5分钟的倍数，（5分钟为一个单位时间），已知从池塘Li到池塘Li+1要化去约翰ti个单位时间，每个池塘的上鱼率预先也是已知的，池塘Li在第一个单位时间内能钓到的鱼为Fi（0≤Fi≤100），并且每过一个单位时间在单位时间内能钓到的鱼将减少一个常数di（0≤di≤100），现在请你编一个程序计算约翰最多能钓到多少鱼。

输入

输入文件第一行为一个整数n，第二行为一个整数h，第三行为n个用空格隔开的整数，表示Fi（i=1,2,…,n），第四行为n个用空格隔开的整数，表示di（i=1,2,…,n），第五行为n-1个用空格隔开的整数，表示ti（i=1,2,…,n-1）

输出

输出一个整数，表示约翰最多能钓到的鱼的数量。

样例输入

2
1 10 1
2 5
2

样例输出

31

Code

#include <stdio.h>
#include <string.h>
#define MS 26

int f[MS],fb[MS],d[MS];
int t[MS]={0};
int res[MS]={0};
int n,k;
int fx[MS]={0};

void init()
{ scanf("%d%d",&n,&k);
k=k*12;
int i;
for(i=1;i<=n;i++)
scanf("%d",&f[i]);
for(i=1;i<=n;i++)
scanf("%d",&fb[i]);
for(i=2;i<=n;i++)
scanf("%d",&d[i]);
for(i=2;i<=n;i++)
t[i]=t[i-1]+d[i];
}

int findmax(int pool)
{ int i,max=0,maxi=0;
for(i=1;i<=pool;i++)
{
if(fx[i]>max)
{
max=fx[i];
maxi=i;
}
}
return maxi;
}

void stopat(int pool)
{ // memcpy(fx,f,MS*sizeof(f[0]));
int i;
for(i=1;i<=n;i++) fx[i]=f[i];
int kx=k;
kx=kx-t[pool];
while(kx>0)
{
int pos=findmax(pool);
if(pos!=0)
{
res[pool]+=fx[pos];
fx[pos]-=fb[pos];
}
kx--;
}
} int main()
{ init();
int i;
for(i=1;i<=n;i++)
stopat(i);
int max=0;
for(i=1;i<=n;i++)
max=res[i]>max?res[i]:max;
// printf("%d\n",res[i]);
printf("%d",max);
return 0;
}