游客 注册 | 登录
中文 | En

1784 - 钓鱼

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

    约翰是个垂钓谜，星期天他决定外出钓鱼h小时（1≤h≤16），约翰家附近共有n个池塘（2≤n≤25），这些池塘分布在一条直线上，约翰将这些池塘按离家的距离编上号，依次为L1,L2,…,Ln，约翰家门外就是第一个池塘，所以他到第一个池塘是不用花时间的，约翰可以任选若干个池塘垂钓，并且在每个池塘他都可以呆上任意长的时间，但呆的时间必须为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

C++解答

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N(16*60/5+5),M(30);  //M:池塘上界  N:单位时间上界 
int tim[M],t[M],first[M],d[M],f[M][N],ans(0);
int main()
{
//    ifstream cin("fish.in");
//    ofstream cout("fish.out");
    int h,n;
    cin>>n>>h;
    h=h*60/5;
    for (int i=1;i<=n;i++) cin>>first[i];
    for (int i=1;i<=n;i++) cin>>d[i]; 
    t[0]=0;
    for (int i=1;i<n;i++) { cin>>tim[i];  t[i]=t[i-1]+tim[i]; }  
    memset(f,0,sizeof(f));
    for (int j=1;j<=h;j++)
        if (first[1]-(j-1)*d[1])
             f[1][j]=first[1]*j-j*(j-1)*d[1]/2;
        else f[1][j]=f[1][j-1]; 
    ans=f[1][h];       
    for (int i=2;i<=n;i++)
        for (int j=t[i-1]+1;j<=h;j++)
        {
            f[i][j]=f[i-1][j-tim[i-1]];
            for (int k=1;k<=j-t[i-1]&&first[i]-(k-1)*d[i]>0;k++)                
                    f[i][j]=max(f[i][j],f[i-1][j-tim[i-1]-k]+k*first[i]-k*(k-1)/2*d[i]);                            
            ans=max(ans,f[i][j]);
        }
    cout<<ans<<endl;
    return 0;
}
请先登陆