线上OJ:
一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1948 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/description/442/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P1070 (opens in a new tab)
还是应证了那句老话:信奥强的人,语文水平都有点#¥%……&()。这道题第一大的难点就是考察大家的阅读理解能力。很多需要仔细斟酌的地方,比如 t 时刻是在道路上?还是在工厂?
佩服那些能在考场上就把这题Ac的同学,只有高手才懂高手在说什么。
核心思想:
一、题目要求的是 “经过m 个单位时间后,扣除购买机器人的花费,小新最多能收集到多少金币”
。我们设 dp[t] 表示经过 t个时间单位后(扣除购买机器人的花费),最多收集多少金币。
二、由于 经过t个时间单位后,小新可能在任意一个工厂。而这个位置有可能是 从前面某个工厂买了机器人并走了k步 后过来的。
三、所以:dp[t]的最优解 一定发生在 经过了k步后的某个i号工厂。这个k我们需要枚举
其中: ;
dp[t-k] + value - cost[st]:表示k步前的最优解,加上这k步所收集到的金币,减去k步前买机器人的花费
value 统计到达i#工厂时路上收集的金币数量,是一个阶段性的前缀和
cost[st] 表示在st号工厂买机器人的花费
四、以上三步基本可以推断出来本题采用动态规划来进行。由于dp[t]的最优解一定发生在经过了k步后的某个i号工厂。所以分三层循环:
第一层循环:枚举经过的时间单位 t。求出dp[t],最终的结果就是dp[m]
第二层循环:枚举经过t个时间单位后,机器人现在在哪个工厂(如果现在在第i号工厂,则上一个工厂是i-1#,上一条道路是i-1#)
第三层循环:因为dp[t]的最优解一定在经过了k步后到达某个i号工厂,故从1~p 枚举步数 k
题解代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n,m,p;
int gold[N][N]; // gold[i][t] 表示第i条道路,在第t个时间单位时可用于收集的金币数量
int cost[N]; // cost[i] 表示第i个工厂购买机器人的花费
int dp[N]; // dp[t]表示经过t个时间单位的时候(扣除购买机器人的花费),最多收集多少金币
// 注意1:第i条道路连接这第 i# 和第 i+1# 工厂。所以如果机器人当前在i#工厂,则它的上一个工厂是i-1,上上个是i-2...
// dp[t]的最优解一定在经过了k步后的某个i号工厂
// dp[t] = max(dp[t], dp[t-k] + value - cost[st]); // 其中value统计到达i#工厂时路上收集的金币数量,是一个阶段性的前缀和。如果dp[t]的最优解是走了k步得到,则dp[t-k]表示k步前的最优解,加上这k步所收集到的金币,减去k步前买机器人的花费
int main()
{
scanf("%d %d %d", &n, &m, &p);
for(int i = 1; i <= n; i++)
for(int t = 1; t <= m; t++)
scanf("%d", &gold[i][t]); // 读入第i条道路,在第t个时间单位时可用于收集的金币数量
for(int i = 1; i <= n; i++)
scanf("%d", &cost[i]); // 读入第i个工厂购买机器人的花费
memset(dp, 0xaf,sizeof(dp));// 初始化为无穷小
dp[0] = 0; // 经过0个时间单位,收集的金币数量为0
for(int t = 1; t <= m; t++) // 第一层枚举经过的时间单位t。因为dp[t]的最优解一定在经过了k步后达到某个i号工厂
{
for(int i = 1; i <= n; i++) // 第二层枚举经过t个时间单位后,机器人现在在哪个工厂(如果现在在第i号工厂,则上一个工厂是i-1#,上一条道路是i-1#)
{
int st = i - 1; // 找起点工厂 st = start
if(st == 0) st = n; // 考虑环
int value = gold[st][t]; // 初始化第一段路径在t时刻的金币数量
for(int k = 1; k <= p; k++) // 因为dp[t]的最优解一定在经过了k步后到达某个i号工厂,故从1~p枚举k
{
if(k > t) break; // 处理边界:如果步数超过时间单位t,则跳出内循环
// 核心语句:value统计到达i#工厂时路上收集的金币数量总和,这其实是一个阶段性的前缀和。cost[st]是指在起点st工厂买机器人时的花费
dp[t] = max(dp[t], dp[t-k] + value - cost[st]);
if( --st == 0) st = n; // 起点工厂向前继续枚举
value += gold[st][t-k];// 每向前继续枚举时,时刻也会减少
}
}
}
printf("%d", dp[m]);
return 0;
}