正題

luogu 7302
金牌導(dǎo)航 數(shù)據(jù)結(jié)構(gòu)優(yōu)化DP-4

---

題目大意

在坐標(biāo)軸上會出現(xiàn)n個金幣，第i個金幣$t_i$時在$w_i$出現(xiàn)（只出現(xiàn)一個單位時間），價值為$s_i$，當(dāng)你$t_i$時在$w_i$，就能獲得該金幣，每個單位時間你最多可以移動兩個單位距離，現(xiàn)在問你最大價值是多少

---

解題思路

由于坐標(biāo)軸較大，所以考慮從n下手

設(shè)f_i為撿到第i個金幣的最大價值，那么有:

$$f_i=\underset{|w_i?w_j|?2\times (t_i?t_j)}{\min }(f_j+s_i)$$

考慮優(yōu)化，先把條件拆開：
$$\{\begin{array}{c}2t_i?w_i?2t_j?w_j(w_i?w_j)\\ 2t_i+w_i?2t_j+w_j(w_i<w_j)\end{array}$$

不難證明：當(dāng)滿足當(dāng)前情況的條件時，另一情況的條件也滿足，那么就是要同時滿足兩個條件

上式是二維偏序，可以先排序，然后用樹狀數(shù)組存儲解決

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 using namespace std; int n, m, bn, b[N], c[N]; struct node {int t, w, s, g1, g2; }a[N]; void add(int x, int y) {for (; x <= 100000; x += x&-x)c[x] = max(c[x], y);return; } int ask(int x) {int g = 0;for (; x; x -= x&-x)g = max(g, c[x]);return g; } bool cmp(node a, node b) {return a.g2 < b.g2; } int main() {scanf("%d%d", &m, &n);for (int i = 1; i <= n; ++i){scanf("%d%d%d", &a[i].t, &a[i].w, &a[i].s);a[i].g1 = 2 * a[i].t - a[i].w;//計算兩個偏序值a[i].g2 = 2 * a[i].t + a[i].w;b[i] = a[i].g1;}sort(b + 1, b + 1 + n);bn = unique(b + 1, b + 1 + n) - b - 1;for (int i = 1; i <= n; ++i)a[i].g1 = lower_bound(b + 1, b + 1 + bn, a[i].g1) - b;//離散化sort(a + 1, a + 1 + n, cmp);for (int i = 1; i <= n; ++i)add(a[i].g1, ask(a[i].g1 - 1) + a[i].s);//第二維偏序printf("%d", ask(100000));return 0; }

總結(jié)

以上是生活随笔為你收集整理的【DP】【树状数组】免费馅饼（luogu 7302/金牌导航 数据结构优化DP-4）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。