洛谷 P1725 琪露诺（线段树优化dp）

题目链接

https://www.luogu.com.cn/problem/P1725

思路

我们令$dp[i]$表示琪露诺移动到第$i$个格子时能够获得的最大冰冻指数。

显然，状态转移方程为：$dp[i]=max(dp[i],dp[k]+a[i])$，其中$k+L\le i$并且$(k+R\ge i)$。

因为$L$和$R$的值很大，所以我们可以使用线段树来进行优化。

使用线段树维护区间$dp[i]$的最大值，每计算出一个新的$dp[i]$，就将其扔到线段树中。我们令编号从$1$开头，则最后的答案为$dp[n+2]$。

代码

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long doubletypedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, l, r;
int a[N], dp[N];
struct segmenttree
{struct node{int l, r, maxx, tag;};vector<node>tree;segmenttree(): tree(1) {}segmenttree(int n): tree(n * 4 + 1) {}void pushup(int u){auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];root.maxx = max(left.maxx, right.maxx);}void pushdown(int u){auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];if (root.tag){left.tag = root.tag;right.tag = root.tag;left.maxx = root.tag;right.maxx = root.tag;root.tag = 0;}}void build(int u, int l, int r){auto &root = tree[u];root = {l, r};if (l == r){root.maxx = -inf;return;}int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}void modify(int u, int l, int r, int val){auto &root = tree[u];if (root.l >= l && root.r <= r){root.maxx = val;root.tag = val;return;}pushdown(u);int mid = root.l + root.r >> 1;if (l <= mid) modify(u << 1, l, r, val);if (r > mid) modify(u << 1 | 1, l, r, val);pushup(u);}int query(int u, int l, int r){auto &root = tree[u];if (root.l >= l && root.r <= r){return root.maxx;}pushdown(u);int mid = root.l + root.r >> 1;int res = -inf;if (l <= mid) res = query(u << 1, l, r);if (r > mid) res = max(res, query(u << 1 | 1, l, r));return res;}
};
void solve()
{cin >> n >> l >> r;fill(dp, dp + 1 + n + 2, -inf);for (int i = 1; i <= n + 1; i++){cin >> a[i];}segmenttree smt(n + 1);smt.build(1, 1, n + 1);dp[1] = a[1];smt.modify(1, 1, 1, dp[1]);for (int i = 2; i <= n + 1; i++){if (i - l < 1){dp[i] = -inf;continue;}dp[i] = max(dp[i], smt.query(1, max(i - r, 1ll), max(i - l, 1ll)) + a[i]);smt.modify(1, i, i, dp[i]);}//n+2表示对岸,包括>n+1的所有格子,所以要特殊处理。dp[n + 2] = smt.query(1, max(n + 2 - r, 1ll), max(n + 2 - 1, 1ll));cout << dp[n + 2] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}