[BZOJ4993||4990] [Usaco2017 Feb]Why Did the Cow Cross the Road II（DP + 线段树）

传送门

f[i][j]表示当前第i个，且最后一个位置连接到j

第一维可以省去，能连边的点可以预处理出来，dp可以用线段树优化

#include <cstdio>#include <iostream>#include <algorithm>#define N 100001#define root 1, 1, n#define ls now << 1, l, mid#define rs now << 1 | 1, mid + 1, rusing namespace std;int n, ans, cnt;int a[N], pos[N], sum[N << 2], f[N];inline int read()inline int query(int now, int l, int r, int x, int y)inline void update(int now, int l, int r, int x, int d)int mid = (l + r) >> 1;if(x <= mid) update(ls, x, d);else update(rs, x, d);sum[now] = max(sum[now << 1], sum[now << 1 | 1]);}int main()}for(i = 1; i <= n; i++) ans = max(ans, f[i]);printf("%d\n", ans);return 0;}

上一篇：[BZOJ1595] [Usaco2008 Jan]人工湖（单调栈）

下一篇：[BZOJ4989] [Usaco2017 Feb]Why Did the Cow Cross the Road（树状数组）