P3431 [POI2005]AUT-The Bus 树状数组+DP

题目链接

题目大意：

Byte City 的街道形成了一个标准的棋盘网络 – 他们要么是北南走向要么就是西东走向. 北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m). Byte City里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)结束.公交车只能往北或往东走. 现在有一些乘客在某些站点等车. 公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.

n和m范围很大，但是我们先考虑如果n和m不那么大的时侯就是一个很简单的DP。转移方程为$dp[i][[j]=a[i][j]+max(dp[i-1][j]+dp[i][j-1]$。然后这种方程的其实就是找一个矩阵的最值，如果我们把$dp[i][j]$初始化为0的话，其实这个方程就变成了$dp[i][j]=a[i][j]+max(dp[x][y]),1<=x<=i,1<=y<=j$。然后我们就可以用前缀和的思想来维护这个矩阵的最值，按照x，y升序排序，y离散化一下，就相当于每次都是维护一行的最值，用树状数组查询和询问，最终复杂度是$k\ast log(k)$

代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const double Pi = acos(-1); namespace { template <typename T> inline void read(T &x) { x = 0; T f = 1;char s = getchar(); for(; !isdigit(s); s = getchar()) if(s == '-') f = -1; for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48); x *= f; } } #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define _srep(n,m,i)for (register int i = (n); i >= (m); i--) #define _sfor(n,m,i)for (register int i = (n); i > (m); i--) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define lowbit(x) x & (-x) #define pii pair<int,int> #define fi first #define se second const int N = 1e5+5; struct node { int x, y, val; bool operator < (const node &a) const { return x == a.x ? y < a.y : x < a.x; } }e[N]; vector<int> ve; int getid(int x) { return lower_bound(ve.begin(),ve.end(), x) - ve.begin() + 1; } int c[N], len; void upd(int pos, int x) { for(; pos <= len; pos += lowbit(pos)) c[pos] = max(x, c[pos]); } int qry(int pos) { int ans = 0; for(; pos; pos -= lowbit(pos)) ans = max(ans, c[pos]); return ans; } int main() { int n, m, k; scanf("%d %d %d", &n, &m, &k); _for(0, k, i) scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].val), ve.push_back(e[i].y); sort(e, e + k); sort(ve.begin(), ve.end()); ve.erase(unique(ve.begin(), ve.end()), ve.end()); len = ve.size(); int ans = 0, res; _for(0, k, i) { e[i].y = getid(e[i].y); res = qry(e[i].y) + e[i].val; ans = max(ans ,res); upd(e[i].y, res); } cout << ans << endl; }