题解 P1717 【钓鱼】

MoonPie · 2019-10-27 22:50:21 · 题解

看到这题题解不多，那就让本蒟蒻来水一篇题解吧！

先看题，是一个求最值问题，在看到数据不大，很容易想到用DP(动态规划)解决

根据题目中的描述：所有数据都是以5分钟为单位的，所以我们也把5分钟作为一个单位， 这样可以方便计算

DP核心：

Firstlly,状态转移方程：

定义dp[i][j]为前i个池塘，总共用时j分钟能钓到最多的鱼的数量

则dp[i][j]的多少取决于再最后一个池塘（第i个池塘）所花的时间

设在最后一个池塘钓了k分钟

根据伟大的高斯的等差数列求和公式，我们化简一下就得到了状态转移方程：

PS：关于k的取值范围：

1.在前i个池塘花的时间为j，所以 j-t[i-1]>=k

2.钓到鱼的数量总>0,所以 (k-1)*d[i]<f[i]

Secondly，DP细节

状态转移方程有了，让我们仔细想想DP的细节

1.由于VIP小朋友可以在任意一个时间结束钓鱼，所以ans=max(dp[i][j])

2.由于VIP小朋友从第i个池塘走到的i+1个池塘要花费t[i]分钟，则到第i个池塘至少花费t[1]+t[2]+……+t[i-1]个单位时间（可以用前缀和sum_t[i]表示）

讲解完毕,已经很清楚了吧!,接下来上代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,h,f[30],d[30],t[30],sum_t[30],dp[30][200],ans;
int main()
{
    cin>>n>>h;
    h=h*12;
    for(int i=1;i<=n;i++) cin>>f[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i<n;i++) 
    {
        cin>>t[i];
        sum_t[i]=sum_t[i-1]+t[i];  //前缀和
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=sum_t[i-1];j<=h;j++)
        {
            for(int k=0;j-t[i-1]-k>=0 && (k-1)*d[i]<f[i];k++)
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j-t[i-1]-k]+k*(f[i]+f[i]-(k-1)*d[i])/2);
                ans=max(dp[i][j],ans);
            }
        }
    }
    cout<<ans;
    return 0;
}