本文主要是介绍SWUN OJ 1749(DP + 线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
SWUN 1749
题目链接
思路：lis一样的状态转移方程，不过要利用线段树去维护，每次更新到i，相应的维护i - d之后的区间的最大值，不断转移即可
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)const int N = 100005;int n, d, A[N];struct Node {int l, r, v;
} node[N * 4];void pushup(int x) {node[x].v = max(node[lson(x)].v, node[rson(x)].v);
}void build(int l, int r, int x = 0) {int mid = (l + r) / 2;node[x].l = l; node[x].r = r; node[x].v = 0;if (l == r) {return;}build(l, mid, lson(x));build(mid + 1, r, rson(x));pushup(x);
}void add(int v, int val, int x = 0) {if (node[x].l == node[x].r) {node[x].v = max(node[x].v, val);return;}int mid = (node[x].l + node[x].r) / 2;if (v <= mid) add(v, val, lson(x));else add(v, val, rson(x));pushup(x);
}int query(int l, int r, int x = 0) {if (r < l) return 0;if (node[x].l >= l && node[x].r <= r)return node[x].v;int mid = (node[x].l + node[x].r) / 2;int ans = 0;if (l <= mid) ans = max(ans, query(l, r, lson(x)));if (r > mid) ans = max(ans, query(l, r, rson(x)));return ans;
}int dp[N];int main() {while (~scanf("%d%d", &n, &d)) {build(0, 100000);int ans = 0;for (int i = 1; i <= d; i++) {scanf("%d", &A[i]);dp[i] = 1;}for (int i = d + 1; i <= n; i++) {scanf("%d", &A[i]);add(A[i - d - 1], dp[i - d - 1]);dp[i] = query(1, A[i] - 1) + 1;ans = max(dp[i], ans);}printf("%d\n", ans);}return 0;
}这篇关于SWUN OJ 1749(DP + 线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
