官方网站数据如何做脚注,哈尔滨网站建立公司,大一网页设计电商网站作业,温州建设诚信网站正题
loj 3264 题目大意
有一个环#xff0c;环上n个点#xff0c;权值为a#xff0c;有m次修改#xff0c;每次修改一个aia_iai#xff0c;然后让你选取一些数#xff0c;使环上不存在连续四个以上的数被选取#xff0c;让你求所选数的最大权值和 解题思路
不难想…正题
loj 3264 题目大意
有一个环环上n个点权值为a有m次修改每次修改一个aia_iai然后让你选取一些数使环上不存在连续四个以上的数被选取让你求所选数的最大权值和 解题思路
不难想到可以用DP做一次DP时间为O(n)m次修改就是O(mn)会TLE
可以先把环剖开那么可以考虑用线段树维护答案
设fi,jf_{i,j}fi,j为当前区间经过左端点选了i个数经过右端点选了j个数
那么区间合并可以枚举两个区间的四个端点然后使中间的点相加不大于4整段选上的特别处理一下
这样合并是O(4^4)的观察下图不难发现倒着枚举第一个区间右端点选的数第二个区间中可以匹配的数是一个前缀和那么可以省掉一维
最后提取出最大的区间然后在左右端点相加不大于4的点中取最大值即可 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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*21node v[N2];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;
}
