P3800 Power收集

题目背景

据说在红雾异变时，博丽灵梦单身前往红魔馆，用十分强硬的手段将事件解决了。

然而当时灵梦在 Power 达到 MAX 之前，不具有“上线收点”的能力，所以她想要知道她能收集多少 P 点，然而这个问题她答不上来，于是她找到了学 OI 的你。

题目描述

可以把游戏界面理解成一个 $N$ 行 $M$ 列的棋盘，有 $K$ 个格子上有 $P$ 点，其价值为 $\operatorname{val}(i,j)$。

初始灵梦可以选择在第一行的任意一个格子出发，每秒她必须下移一格。

灵梦具有一个左右移动的速度 $T$，可以使她每秒向左或右移动至多 $T$ 格，也可以不移动，并且不能折返。移动可视为瞬间完成，不经过路途上的点，只能获得目标格子的 P 点。

求最终她能获得的 POWER 值最大是多少？

输入格式

第一行四个数字，$N,M,K,T$。

接下来 $K$ 行每行 $3$ 个数字 $x,y,v$，代表第 $x$ 行第 $y$ 列有一个 $val$ 为 $v$ 的 P 点，数据保证一个格子上最多只有 $1$ 个 P 点。

输出格式

一个数字

输入输出样例 #1

输入 #1

3 3 4 1
1 1 3
1 2 1
2 2 3
3 3 3

输出 #1

9

说明/提示

对于 $40\%$ 的测试点，$1 \le N,M,T,K \le 200$。

对于 $100\%$ 的测试点，$1 \le N,M,T,K \le 4000$。

$v \le 100$，$N,M,K,T$ 均为整数。

参考代码

-by

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;

const LL Maxk = 4000 + 5;

struct node {
    LL x, y, val;
}vct[Maxk];

LL dp[Maxk];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    LL n, m, k, t;
    cin >> n >> m >> k >> t;
    for (LL i = 0; i < k; ++i)  cin >> vct[i].x >> vct[i].y >> vct[i].val;

    sort(vct, vct + k, [](const node& a, const node& b) {return a.x < b.x;});

    LL res = 0;
    for (LL i = 0; i < k; ++i) {
        dp[i] = vct[i].val;
        for (LL j = 0; j < i; ++j) {
            if (abs(vct[i].y - vct[j].y) <= t * abs(vct[i].x - vct[j].x))
                dp[i] = max(dp[i], dp[j] + vct[i].val);
        }
        res = max(res, dp[i]);
    }

    cout << res;

    return 0;
}