本文主要是介绍POJ 2750 环上线段树 略带DP 的线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求一个环上的最大连续子列的和。但是这个区间不能是整个换。
做法：
把环拆开。
对于最大连续子列，有两种情况
第一种情况，子列在 1~n 中，这样便可以直接求出
第二种情况，子列既包括 1 又包括 n ，首先 最大列和最小列应该是不重合的（除非全是正数），如果重合，假设重合点是正数，则最小列可以更小，如果重合点是负数，则最大列可以更大，矛盾，然后，最大列和最小列应该全部覆盖整个环，证明和上面差不多。
所以，可能情况就是 1~n 中最大列 或者 总和减去 1~n 中最小列 。
至于题中那个不能全部选择的限制，判断一下最小的列是不是负数就可以啦。
略带 dp 是因为从下面向上面转移的时候，有些像 dp 那。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <set>
#include <stack>using namespace std;#define READ freopen("acm.in","r",stdin)
#define WRITE freopen("acm.out","w",stdout)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define MII map<int,int>::iterator
#define fst first
#define sec second
#define MS(x,d) memset(x,d,sizeof(x))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ROOT 0,n-1,1
#define PB push_back
#define FOR(a,b,c) for(int a=b;a<c;a++)
#define MOD 1000000007
#define keyTree (ch[ ch[root][1] ][0])
#define MAX 111111struct node
{int sum;int mmin,mmax;int lmax,rmax,lmin,rmin;node(int x){sum=mmin=mmax=lmax=lmin=rmax=rmin=x;}node(){}
}data[MAX<<2];
void PushUp(node &x,node l,node r)
{x.sum=l.sum+r.sum;x.lmax=max(l.lmax,l.sum+r.lmax);x.lmin=min(l.lmin,l.sum+r.lmin);x.rmax=max(r.rmax,r.sum+l.rmax);x.rmin=min(r.rmin,r.sum+l.rmin);x.mmax=max(max(l.mmax,r.mmax),l.rmax+r.lmax);x.mmin=min(min(l.mmin,r.mmin),l.rmin+r.lmin);
}
void update(int p,int x,int l,int r,int rt)
{if(l==r){data[rt]=node(x);return ;}int m=(l+r)>>1;if(p<=m)update(p,x,lson);elseupdate(p,x,rson);PushUp(data[rt],data[rt<<1],data[rt<<1|1]);
}
int num[MAX];
void build(int l,int r,int rt)
{if(l==r){data[rt]=node(num[l]);return ;}int m=(l+r)>>1;build(lson);build(rson);PushUp(data[rt],data[rt<<1],data[rt<<1|1]);
}
int main()
{READ;int n;while(scanf("%d",&n)!=EOF){MS(data,0);int tot=0;for(int i=1;i<=n;i++)scanf("%d",&num[i]),tot+=num[i];build(1,n,1);int m;scanf("%d",&m);for(int i=0;i<m;i++){int p,c;scanf("%d%d",&p,&c);tot=tot+c-num[p];num[p]=c;update(p,c,1,n,1);if(data[1].mmin>0)cout<<tot-data[1].mmin<<endl;elsecout<<max(data[1].mmax,tot-data[1].mmin)<<endl;}} return 0;
}这篇关于POJ 2750 环上线段树 略带DP 的线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
