LuoguP1717 钓鱼

题面

题目分析

动态规划。

\(\bullet\) 设计状态。
思考：我从哪里来？从上一个湖过来。
我到哪里去？到下一个湖去 \(or\) 继续在这个湖钓鱼。
设 \(dp[pos][tim]\) 为前 \(pos\) 个湖花费了 \(tim\) 分钟所能钓的最大的鱼数量。

\(\bullet\) 转移状态。（为了方便计算，我们将题目中的数据全部除以 \(5\)，结果不变。）
\(c\) 表示已经在当前第 \(pos\) 个湖停留钓鱼了 \(c\) 分钟。
\(fish[i]\) 表示第 \(i\) 个湖最多钓的鱼。
\(t\) \(d\) 含义同原题题面的解释。

转移方程：\(dp[pos][tim]=max(dp[pos-1][tim-t[pos-1]-c]+\sum_{i=0}^{c-1}(fish[pos]-i*d[pos]))\)
为了方便计算，我们将这个式子用等差数列求和公式展开后半部分。
即：\(dp[pos][tim]=max(dp[pos-1][tim-t[pos-1]-c]+c*(fish[pos]+fish[pos]-(c-1)*d[pos])/2)\)

解释含义：\(tim-t[pos-1]-c\) 表式上一个湖结束钓鱼时已花费的时间。（当前时间-从上个湖到当前湖花费的时间-当前湖已经花费的时间。）

代码

依题意枚举 \(pos\) \(tim\) \(c\)。

注意：
\(\bullet\) 注意含有减法下标的越界情况。
\(\bullet\) 若 \(dp[pos-1][tim-t[pos-1]-c]\) 还没赋值，continue。
\(\bullet\) 若当前能获得的鱼 \(<=0\)，continue。

代码实现：

#include <bits/stdc++.h>
#define int long long
const int N = 10005;
using namespace std;
inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-'){
            w = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}
int n,h,fish[N],d[N],t[N];
int dp[105][N];
signed main(){
    n = read(),h = read();
    h *= 12;
    for (int i = 1;i <= n;i++){
        fish[i] = read();
    }
    for (int i = 1;i <= n;i++){
        d[i] = read();
    }
    for (int i = 1;i <= n - 1;i++){
        t[i] = read();
    }
    int ans = -1;
    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    for (int pos = 1;pos <= n;pos++){
    	for (int tim = 0;tim <= h;tim++){
    		for (int c = 0;tim - t[pos - 1] - c >= 0;c++){
    			if (dp[pos - 1][tim - t[pos - 1] - c] != -1 && fish[pos] - (c - 1) * d[pos] > 0){
    				dp[pos][tim] = max(dp[pos][tim],dp[pos - 1][tim - t[pos - 1] - c] + c * (fish[pos] + fish[pos] - (c - 1) * d[pos]) / 2);
    				ans = max(ans,dp[pos][tim]);
				}
			}
		}
	}
	printf("%lld",ans);
    return 0;
}