HDU 6447 YJJ’s Salesman
题目
给一个二维数组，从（0，0）走到（1e9, 1e9）。每次只能走右，下，右下，三个方向。其中只有通过右下走到特定给出的点（村庄）时才会获得分值。问最后走到终点最大分值。
分析
很明显的 DP 题目。状态转移题目都给出了。但是 1e9 很明显会爆。
想一下，题目让求最大分值，而最大分值只与特定的点有关。也就是说数组的列上如果没有村庄怎么走都没关系。只关心有村庄的列。也就是只关心 y 坐标。
因为数据太大，可以先将 y 坐标离散化。
我们从左往右看每一列的村庄，对于第 i 个村庄，坐标为（x，y），dp [i] 表示走到村庄 i 所能得到最大分值。由于只能从左上方来，dp[i]=max(dp[i],dp[j]+1)dp[i] = max(dp[i], dp[j]+1)dp[i]=max(dp[i],dp[j]+1)
这里的 j 村庄指的是坐标符合 xj<x,yj<y−1x_j < x,y_j < y-1xj<x,yj<y−1。
也就是第 i 个村庄左上方的所有村庄，不相邻也没关系，可以想象中间的路全部都是右、下。
现在问题变成找 1~y 最大的 dp【j】。可以用树状数组前缀最值。
每次找完一列，再将一列的 dp 值全部更新。（因为 xj<xx_j < xxj<x)
#include <bits/stdc++.h>using namespace std;#define ll long long #define INF 0x3f3f3f3f#define fuck(x) cout<<x<<endlconst int N = 1e5 + 5;const ll mod = 1e9 + 7;int t, n, cnt;int tmp[N], c[N];struct node{int x, y, w;bool operator < (const node &b) const{return x < b.x;}} a[N];//保存 村庄点对void update(int x, int val){// 树状数组维护前缀最值while(x <= cnt){c[x] = max(c[x], val);x += (x & -x);}}int query(int x){int res = 0;while(x > 0){res = max(res, c[x]);x -= (x & -x);}return res;}int dp[N];void DP(){for(int i = 0; i < n; i++){dp[i] = a[i].w;}int pos, ans;pos = ans = 0;for(int i = 0; i < n; i++){while(pos < i && a[pos].x < a[i].x){update(a[pos].y, dp[pos]);pos++;}dp[i] = query(a[i].y - 1) + a[i].w; // dp[i] = max(dp[i], dp[j]+w)ans = max(ans, dp[i]);}printf("%d\n", ans);}int main(){scanf("%d", &t);while(t--){scanf("%d", &n);memset(c, 0, sizeof(c));for(int i = 0, x, y, w; i < n; i++){scanf("%d%d%d", &x, &y, &w);a[i] = {x, y, w};}cnt = 0; // 离散化 yfor(int i = 0; i < n; i++){tmp[cnt++] = a[i].y;}sort(tmp, tmp + cnt); // 排序去重cnt = unique(tmp, tmp + cnt) - tmp;//unique()函数将重复的元素放到的尾部 //然后返回指向第一个重复元素的迭代器for(int i = 0; i < n; i++){a[i].y = lower_bound(tmp, tmp + cnt, a[i].y) - tmp + 1;}sort(a, a + n);DP();}return 0;}/**/
