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;
}

/*
*/