Description

信息組最近貓成災了!隔壁物理組也拿貓沒辦法.信息組組長只好去請神刀手來幫他們消滅貓.信息組現在共有n 只貓(n 為正整數),編號為1 到n,站成了一個環,第i 只貓的左邊是第i-1 只貓,右邊是第i+1 只貓.特別的,第1 只貓的左邊是第n 只貓,第n 只貓的右邊是第1 只貓.每只貓擁有價值,表示消滅它能給信息組組長帶來的聲譽.注意,有的貓價值為負數,這意味著消滅它會損害組長的聲譽.神刀手可以選擇一些貓消滅掉.但是,我們的組長實際上非常喜歡貓,他希望神刀手不要消滅兩只相鄰的貓.
神刀手的能力組長現在還不知道.所以,組長希望知道對于所有的1<=m<=n/2,如果神刀手剛好消滅m 只貓,他最多能獲得的聲譽.信息組組長當然知道怎么做啦！但是他想考考你……

Input

從cat.in 中讀入數據第一行包括一個正整數n第二行為n 個整數,依次代表第1,2,…,n 只貓的價值.

Output

輸出到文件cat.out輸出共n/2 行,第i 行表示假如神刀手剛好消滅i 只貓,信息組組長最多能獲得的收益.

Sample Input

輸入1：

811 8 1 1 9 1 1

輸入2：

115 6 7 8 9 10 9 8 7 6 5

Sample Output

輸出1：

9171812

輸出2：

1018263238

Data Constraint

對于30%的數據,滿足n<=20
對于60%的數據,滿足n<=2000
對于另外20%的數據,滿足n 為偶數
對于100%的數據,滿足1<=n<=200000,|每只貓的價值|<=1e9

Solution

• 事實上 JZOJ 4726 種花 與這道題有異曲同工之妙，詳見我的博客：

• JZOJ 4726. 【NOIP2016提高A組模擬8.22】種花

• 都是使用堆，貪心地選取較大的那個，之后將其兩邊的刪去、并加入堆中，

• 這樣的相當于撤銷操作的做法就可以保證正確性。

• 于是我們每選取一次，就統計并輸出答案即可，時間復雜度 O(N?log?N) 。

Code

#include<cstdio> #include<queue> using namespace std; const int N=2e5+1; struct data {long long x;int y;bool operator <(const data &z)const{return x<z.x;} }t; long long ans; long long a[N]; int l[N],r[N]; bool bz[N]; priority_queue<data>q; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void work(int x) {bz[x]=true;l[r[x]]=l[x];r[l[x]]=r[x]; } int main() {int n=read();for(int i=1;i<=n;i++){t.x=a[t.y=i]=read();q.push(t);l[i]=i>1?i-1:n;r[i]=i<n?i+1:1;}n>>=1;while(n--){for(t=q.top();bz[t.y];t=q.top()) q.pop();q.pop();ans+=t.x;t.x=a[t.y]=a[l[t.y]]+a[r[t.y]]-t.x;q.push(t);work(l[t.y]);work(r[t.y]);printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5372. 【NOIP2017提高A组模拟9.17】猫的全部內容，希望文章能夠幫你解決所遇到的問題。

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