[DP/贪心 时间] P1717 钓鱼

[DP 时间] P1717 钓鱼

​​题目链接​​

题目

思路

贪心可以做的比较简单，不过这里打算练习一下DP写法

为了简化计算，把5分钟设为单位时间
状态表示
表示走到第i个湖钓鱼，耗时j
属性：max
状态计算
去下一个池塘

在这个池塘钓k个单位时间


注意原本写错了写成

这个转移有问题,钓k次应该是从原本没到第i个池塘时间转移过来的，所以应该是路程

两个式子可以合并
目标

代码

// Problem: P1717 钓鱼
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1717
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// FishingRod
// 参考：https://www.luogu.com.cn/blog/68706/solution-p1717

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
typedef pair<int,int> PII;
//#define MULINPUT
/*DATA & KEY

*/
const int N=1E3+10,M=110;
LL dp[N][N];
LL t[M],d[M],f[M];
LL ans;
void solve(int C)
{
  //NEW DATA CLEAN
  
  //NOTE!!!
  int n,T;cin>>n>>T;
  T=T*12;
  for(int i=1;i<=n;i++)cin>>f[i];
  for(int i=1;i<=n;i++)cin>>d[i];
  for(int i=2;i<=n;i++)cin>>t[i];
  
  for(int i=1,st=t[1];i<=n;st+=t[i+1],i++)//到i个池塘
    for(int j=st;j<=T;j++)//枚举到i的用时
      for(int k=0;k<=j-st;k++)//枚举钓了k个单位时间
      {
        dp[i][j]=max(dp[i][j],dp[i-1][j-t[i]-k]+max((LL)0,k*f[i]-k*(k-1)/2*d[i]));
        ans=max(ans,dp[i][j]);
      }
  cout<<ans<<endl;
}

int main()
{
  #ifdef MULINPUT
    scanf("%d",&T);
    for(int i=1;i<=T;i++)solve(i);
  #else
    solve(1);
  #endif
  return 0;
}