网易云播放器做网站播放/营销推广模式有哪些

传送门

题意：

从 (0,0)往 (10^9,10^9) 走，每次只能从 (x,y) 走到(x+1,y) 或者 (x,y+1) 或者 (x+1,y+1)，不能折返，不能走重复的路，

在地图上分布着一些村庄，给出村庄的坐标(x,y) 和 v值，当且仅当你从(x−1,y−1) 走到村庄时，你才可以获得 v，求最大能获得多少 v。

题解：

显然，假设我走到了某一个村庄 (x0,y0)，那么只有在 x≥x0+1且 y≥y0+1 范围内的村庄，能使得我的 v 值进一步增加，

换句话说，我走到了某一个村庄 (x0,y0)，我上一个走到的“有意义的”村庄必然是在 x≤x0−1 且y≤y0−1 的范围内的，

那么我就要在 x≤x0−1 且 y≤y0−1 的范围内找到某个村庄，我走到该村庄时，我获得的 v 值时最大的，

故，我们假设 dp[i]为走到村庄 ii 时能获得的最大的 v，则状态转移方程为：

dp[i]=max(dp[j]+v[i])，其中村庄 jj 的坐标(x,y) 满足x≤x0−1 且y≤y0−1

那么，简单地说，对于每个村庄，要能 O(log⁡n) 获得某区域内的最大值，同时也要能O(log⁡n) 的某区域内的最大值，自然而然想到树状数组……

我们离散化纵坐标，并且从小到大枚举横坐标，用树状数组维护纵坐标为 [1,y] 区域内最大的dp[i]，

1、计算到某个横坐标值上某一村庄 dp[i]，假设其纵坐标为 y，查询[1,y−1] 区域内最大值；

2、每次计算完某个横坐标值的一竖条上的所有村庄的dp[i]，将这一竖条上所有的dp[i] 全部拿去更新树状数组。

附上代码：

#include <bits/stdc++.h>using namespace std;struct Node {int x, y, v;void input() {scanf("%d%d%d", &x ,&y, &v);}
}node[100010];bool cmp(Node a, Node b) {return a.x < b.x;
}int a[100010];
int tot;int c[100010];
int lowbit(int x) {return x&(-x);
}void update(int i, int val) {while (i <= tot) {c[i] = max(c[i], val);i += lowbit(i);}
}int query(int i) {int res = 0;while (i > 0) {res = max(res, c[i]);i -= lowbit(i);}return res;
}int dp[100010];int main() {int T;int n;scanf("%d", &T);while (T--) {scanf("%d", &n);for (int i = 0; i < n; i++)node[i].input();tot = 0;for (int i = 0; i < n; i++) {a[tot++] = node[i].y;}sort(a, a+tot);tot = unique(a, a+tot) - a;for (int i = 0; i < n; i++) {node[i].y = lower_bound(a, a+tot, node[i].y) - a + 1;}sort(node, node+n, cmp);for (int i = 0; i < n; i++) dp[i] = node[i].v;for (int i = 1; i <= tot; i++) c[i] = 0;int pos = 0;int ans = 0;for (int i = 0; i < n; i++) {while (pos < i && node[pos].x < node[i].x) {update(node[pos].y, dp[pos]);pos++;}dp[i] = query(node[i].y - 1) + node[i].v;ans = max(ans, dp[i]);}printf("%d\n",ans);}return 0;
}