HDU 6447 YJJ's Salesman（树状数组优化DP + 离散化）

​​HDU 6447 YJJ’s Salesman​​

题目

给一个二维数组，从（0，0）走到（1e9, 1e9）。每次只能走右，下，右下，三个方向。其中只有通过右下走到特定给出的点（村庄）时才会获得分值。问最后走到终点最大分值。

分析

很明显的 DP 题目。状态转移题目都给出了。但是 1e9 很明显会爆。

想一下，题目让求最大分值，而最大分值只与特定的点有关。也就是说数组的列上如果没有村庄怎么走都没关系。只关心有村庄的列。也就是只关心 y 坐标。

因为数据太大，可以先将 y 坐标离散化。

我们从左往右看每一列的村庄，对于第 i 个村庄，坐标为（x，y），dp [i] 表示走到村庄 i 所能得到最大分值。由于只能从左上方来，

这里的 j 村庄指的是坐标符合。

也就是第 i 个村庄左上方的所有村庄，不相邻也没关系，可以想象中间的路全部都是右、下。

现在问题变成找 1~y 最大的 dp【j】。可以用树状数组前缀最值。

每次找完一列，再将一列的 dp 值全部更新。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 0x3f3f3f3f
#define fuck(x) cout<<x<<endl
const 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;            // 离散化 y
        for(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;
}

/*
*/