1373：鱼塘钓鱼(fishing）

【题目描述】

有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：

鱼塘编号每1分钟能钓到的鱼的数量（1..1000）每1分钟能钓鱼数的减少量（1..100）当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）11023214453206441654593

即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……

给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。

假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

【输入】

共5行，分别表示：

第1行为N；

第2行为第1分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；

第3行为每过1分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；

第4行为当前鱼塘到下一个相邻鱼塘需要的时间；

第5行为截止时间T。

【输出】

一个整数（不超过231−1

），表示你的方案能钓到的最多的鱼。

【输入样例】

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

【输出样例】

76

 我们可以进行枚举，到第i个池塘得到的最大方案，且最后停留在第i个池塘上。

#include<bits/stdc++.h>
using namespace std;
#define N 100+1
#define T 1000+1
int n,a[N],b[N],c[N],s[N],t,maxx=-1;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<n;i++)cin>>c[i];
    cin>>t;
    for(int i=1;i<=n;i++)c[i]+=c[i-1];
    for(int i=1;i<=n;i++)
    {
        int tim=t-c[i-1],ans=0;
        for(int j=1;j<=n;j++)s[j]=a[j];
        for(int j=1;j<=tim;j++)
        {
            int pos=0;
            for(int k=1;k<=i;k++)
                if(s[k]>s[pos])pos=k;
            if(pos==0)break;
            ans+=s[pos];
            s[pos]-=b[pos];
        }
        maxx=max(maxx,ans);
    }
    cout<<maxx<<endl;
}