《P3800 Power 收集》

题目背景

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

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

题目描述

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

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

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

求最终她能获得的所有 P 点的价值总和最大是多少？

输入格式

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

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

输出格式

一个整数，表示灵梦能获得的 P 点的价值总和的最大值。

输入输出样例

输入 #1复制

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

输出 #1复制

9

说明/提示

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

对于 100% 的测试点，1≤N,M,T,K≤4000，0≤v≤100，N,M,K,T 均为整数。

by-szc

代码实现：

#include <stdio.h> #include <set> #include <algorithm> using namespace std; int n, m, k, t; struct P { int x, y, v; bool operator < (const P &b) const { if (this->v == b.v) { if (this->x == b.x) return this->y < b.y; return this->x < b.x; } return this->v > b.v; } }; inline bool cmp(const P &a, const P &b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x; } P arr[4010]; int main() { scanf("%d%d%d%d", &n, &m, &k, &t); for (P *p = arr; p < arr + k; p++) scanf("%d%d%d", &(p->x), &(p->y), &(p->v)); sort(arr, arr + k, cmp); int res = arr[0].v; set<P> s; s.insert(arr[0]); for (int i = 1; i < k; i++) { for (set<P>::iterator it = s.begin(); it != s.end(); it++) { if (abs(arr[i].y - it->y) <= (arr[i].x - it->x) * t) { arr[i].v += it->v; break; } } s.insert(arr[i]); if (arr[i].v > res) res = arr[i].v; } printf("%d\n", res); return 0; }