pot
Description

這個假期，小h在自家院子里種了許多花，它們圍成了一個圈，從1…n編號（n<=100000），小h 對每盆花都有一個喜好值xi,（-1000<=xi<=1000）,小h現(xiàn)在覺得這樣一成不變很枯燥，于是他做了m(m<=100000)個改動，每次把第ki盤花改成喜好值為di的花，然后小h要你告訴他，在這個花圈中，連續(xù)的最大喜好值是多少。

Input

第一行，n，花盆的數(shù)量
第二行，n個數(shù)，表示對于每盆花的喜好值。
第三行：m, 改動的次數(shù)
以下m行，每行兩個數(shù)ki 和di 。

Output

M行，每一行對應(yīng)一個更改，表示連續(xù)的最大喜好值，且不能整圈都選。（注意：是在圈上找）

Sample Input

5

3 -2 1 2 -5

4

2 -2

5 -5

2 -4

5 -1

Sample Output

4

4

3

5

題解：
對于20分，當(dāng)然是用一個暴力過去啦~~~
對于30分，用O(nm)的動態(tài)規(guī)劃，再加上卡常數(shù)就好了。
對于100分，此題滿分做法涉及到線段樹，不懂的可以去了解一下。
本題題意是數(shù)形成一個環(huán)狀，又說了不可以全部數(shù)選擇。那么，我們只需要求出1到n內(nèi)最大的子區(qū)間和；從兩邊開始選的最大子區(qū)間和；1到n內(nèi)最小的子區(qū)間和；從兩邊開始選的最小子區(qū)間和。因為我們要求出這樣的東東：




那么，最優(yōu)答案就是sum（表示數(shù)環(huán)的總和）-min或max。這時，我們用線段樹來做這些操作，然后大體細(xì)節(jié)就好好看題，筆玩一下就可以推出線段樹維護的規(guī)律。
來給個偽程序來維護max和min的操作：

{v為當(dāng)前樹的深度} tree[v].sum:=tree[v*2].sum+tree[v*2+1].sum;{求sum值} tree[v].max:=max(max(tree[v*2].max,tree[v*2+1].max),tree[v*2].rgss+tree[v*2+1].lgss);{求max的值} tree[v].lgss:=tree[v*2].lgss;{左邊的maxlgss值} tree[v].rgss:=tree[v*2+1].rgss;{右邊的maxrgss值} tree[v].min:=min(min(tree[v*2].min,tree[v*2+1].min),tree[v*2].mrgss+tree[v*2+1].mlgss);{求min的值} tree[v].mlgss:=tree[v*2].mlgss{求左邊的minlgss值}; tree[v].mrgss:=tree[v*2+1].mrgss{求右邊的minrgss值};if(tree[v*2].lgss<tree[v*2].sum+tree[v*2+1].lgss) thenbegintree[v].lgss:=tree[v*2].sum+tree[v*2+1].lgss;end;if(tree[v*2+1].rgss<tree[v*2+1].sum+tree[v*2].rgss) thenbegintree[v].rgss:=tree[v*2+1].sum+tree[v*2].rgss;end;if(tree[v*2].mlgss>tree[v*2].sum+tree[v*2+1].mlgss) thenbegintree[v].mlgss:=tree[v*2].sum+tree[v*2+1].mlgss;end;if(tree[v*2+1].mrgss>tree[v*2+1].sum+tree[v*2].mrgss) thenbegintree[v].mrgss:=tree[v*2+1].sum+tree[v*2].mrgss;end;

解答問題1：lgss和rgss有何用？答：這個可以時刻維護max的求值，具體維護法筆玩一下，這里不多說。（因為要說明就要畫圖）
解答問題2：如何判斷有沒有全部選。答：這是廢話，只需要判斷max值與sum值相不相等。
解答問題3：為什么sum要在樹內(nèi)做。答：這可以更好地去維護maxlgss、maxrgss、minlgss、minrgss的操作，當(dāng)然時間會更快的問題我就不確定了。
解答問題4：線段樹怎么做。答：自己研究。

標(biāo)程：

typenew=recordmax:longint;lgss:longint;rgss:longint;min:longint;mlgss:longint;mrgss:longint;sum:longint;end;vari,j,k,l,n,m,t,r,x,gb,ans:longint;a:array[0..1000000] of longint;tree:array[0..1000000] of new;bz:boolean; function max(x,y:longint):longint; beginif x>y then exit(x)else exit(y); end; function min(x,y:longint):longint; beginif x<y then exit(x)else exit(y); end; procedure maketree(x,st,en:longint); varm:longint; begintree[x].max:=-50001;tree[x].min:=50001;tree[x].lgss:=-50001;tree[x].rgss:=-50001;tree[x].mlgss:=50001;tree[x].mrgss:=-50001;if st=en thenbeginexit;endelsebeginm:=(st+en) div 2;maketree(x+x,st,m);maketree(x+x+1,m+1,en);end; end; procedure changenumber(v,x,l,r:longint); vari,j,mid:longint; beginif l=r thenbegintree[v].max:=gb;tree[v].min:=gb;tree[v].lgss:=gb;tree[v].rgss:=gb;tree[v].mlgss:=gb;tree[v].mrgss:=gb;tree[v].sum:=gb;exit;end;mid:=(r+l) div 2;if x>mid thenbeginchangenumber(v*2+1,x,mid+1,r);endelseif x<=mid thenbeginchangenumber(v*2,x,l,mid);end;tree[v].sum:=tree[v*2].sum+tree[v*2+1].sum;tree[v].max:=max(max(tree[v*2].max,tree[v*2+1].max),tree[v*2].rgss+tree[v*2+1].lgss);tree[v].lgss:=tree[v*2].lgss;tree[v].rgss:=tree[v*2+1].rgss;tree[v].min:=min(min(tree[v*2].min,tree[v*2+1].min),tree[v*2].mrgss+tree[v*2+1].mlgss);tree[v].mlgss:=tree[v*2].mlgss;tree[v].mrgss:=tree[v*2+1].mrgss;if(tree[v*2].lgss<tree[v*2].sum+tree[v*2+1].lgss) thenbegintree[v].lgss:=tree[v*2].sum+tree[v*2+1].lgss;end;if(tree[v*2+1].rgss<tree[v*2+1].sum+tree[v*2].rgss) thenbegintree[v].rgss:=tree[v*2+1].sum+tree[v*2].rgss;end;if(tree[v*2].mlgss>tree[v*2].sum+tree[v*2+1].mlgss) thenbegintree[v].mlgss:=tree[v*2].sum+tree[v*2+1].mlgss;end;if(tree[v*2+1].mrgss>tree[v*2+1].sum+tree[v*2].mrgss) thenbegintree[v].mrgss:=tree[v*2+1].sum+tree[v*2].mrgss;end; end; begin//assign(input,'xds.in');reset(input);//assign(output,'xds.out');rewrite(output);readln(n);maketree(1,1,n);for i:=1 to n dobeginread(a[i]);end;for i:=1 to n dobegingb:=a[i];changenumber(1,i,1,n);end;readln(m);for k:=1 to m dobeginreadln(l,r);gb:=r;changenumber(1,l,1,n);if(tree[1].max=tree[1].sum) thenbeginwriteln(tree[1].max-tree[1].min);continue;end;if(tree[1].max>=tree[1].sum-tree[1].min) thenbeginwriteln(tree[1].max);continue;end;if(tree[1].max<tree[1].sum-tree[1].min) thenbeginwriteln(tree[1].sum-tree[1].min);end;end; end.

轉(zhuǎn)載于:https://www.cnblogs.com/RainbowCrown/p/11148449.html

總結(jié)

以上是生活随笔為你收集整理的2017.2.12【初中部 GDKOI】模拟赛B组 T4：pot的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。