正題

loj 3264

---

題目大意

有一個環，環上n個點，權值為a，有m次修改，每次修改一個$a_i$，然后讓你選取一些數，使環上不存在連續四個以上的數被選取，讓你求所選數的最大權值和

---

解題思路

不難想到可以用DP做，一次DP時間為O(n)，m次修改就是O(mn)會TLE

可以先把環剖開，那么可以考慮用線段樹維護答案

設$f_{i,j}$為當前區間經過左端點選了i個數，經過右端點選了j個數

那么區間合并可以枚舉兩個區間的四個端點，然后使中間的點相加不大于4（整段選上的特別處理一下）

這樣合并是O(4^4)的，觀察下圖，不難發現倒著枚舉第一個區間右端點選的數，第二個區間中可以匹配的數是一個前綴和，那么可以省掉一維

最后提取出最大的區間，然后在左右端點相加不大于4的點中取最大值即可

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 40010 using namespace std; int n, m, x; ll y, w[N]; struct node {int num;ll f[4][4]; }; node merge(node a, node b)//合并線段樹 {node c;ll sum;memset(c.f, 0, sizeof(c.f));c.num = a.num + b.num;for (int i = 0; i <= min(3, a.num); ++i)for (int j = 0; j <= min(3, b.num); ++j){if (i == a.num && j == b.num)//兩端都全選{if (i + j <= 3) c.f[i + j][i + j] = a.f[i][i] + b.f[j][j];continue;}if (i == a.num)//第一段全選{for (int k = 0; k <= min(3 - i, b.num); ++k)c.f[i + k][j] = max(c.f[i + k][j], a.f[i][i] + b.f[k][j]);continue;}if (j == b.num)//第二段全選{for (int k = 0; k <= min(3 - j, a.num); ++k)c.f[i][j + k] = max(c.f[i][j + k], a.f[i][k] + b.f[j][j]);continue;}sum = 0;for (int k = 3; k >= 0; --k){sum = max(sum, b.f[3 - k][j]);//前綴和c.f[i][j] = max(c.f[i][j], sum + a.f[i][k]);}}return c; } ll get(node x) {ll ans = 0;for (int i = 0; i <= 3; ++i)for (int j = 0; j <= 3 - i; ++j)//左右端點之和不大于3ans = max(ans, x.f[i][j]);return ans; } struct Tree {#define ls x*2#define rs x*2+1node v[N<<2];void build(int x, int l, int r){if (l == r){v[x].num = 1;v[x].f[1][1] = w[l];return;}int mid = l + r >> 1;build(ls, l, mid);build(rs, mid + 1, r);v[x] = merge(v[ls], v[rs]);return;}void change(int x, int l, int r, int y){if (l == r){v[x].f[1][1] = w[l];return;}int mid = l + r >> 1;if (y <= mid) change(ls, l, mid, y);else change(rs, mid + 1, r, y);v[x] = merge(v[ls], v[rs]);return;} }T; int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%lld", &w[i]);T.build(1, 1, n);printf("%lld\n", get(T.v[1]));scanf("%d", &m);while(m--){scanf("%d%lld", &x, &y);w[x] = y;T.change(1, 1, n, x);printf("%lld\n", get(T.v[1]));}return 0; }

總結

以上是生活随笔為你收集整理的【线段树】海报（loj 3264）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。