p1484 種樹

傳送門

題目

cyrcyr今天在種樹，他在一條直線上挖了n個坑。這n個坑都可以種樹，但為了保證每一棵樹都有充足的養料，cyrcyr不會在相鄰的兩個坑中種樹。而且由于cyrcyr的樹種不夠，他至多會種k棵樹。假設cyrcyr有某種神能力，能預知自己在某個坑種樹的獲利會是多少（可能為負），請你幫助他計算出他的最大獲利。

輸入格式：

第一行，兩個正整數n,k。

第二行，n個正整數，第i個數表示在直線上從左往右數第i個坑種樹的獲利。

輸出格式：

輸出1個數，表示cyrcyr種樹的最大獲利。

分析

首先我們先考慮k=1的情況，則答案即為所有數的最大值。然后我們在考慮k=2的情況，這是我們有兩種選擇：1.在選擇原本的所有數中的最大值ai的同時選一個與它不相鄰的數aj；2.不選擇ai，而選擇ai-1和ai+1。我們推而廣之便可以得到這個題的策略：每一次選堆中最大的元素，將以這個元素為中心的li和ri將會產生的影響放入堆中（因為以某點為中心可能不止向兩側擴展一次，所以要用lr數組記錄），我們要注意每次產生的影響是ali+ari-ai，因為這樣下一次選這兩個點便可以將其上一次擴展的影響覆蓋了。注意每一次擴展的lr要打一個標記以防止被以其他點為中心的點二次訪問，每一次更新lr也要注意將其更新成lli和rri，因為某點的左右邊界的點也可能擴展過。最后我們要注意如果哪一次堆頂元素為非正數就代表這之后任何擴展都不能給答案帶來正效應了，直接跳出循環即可。

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
#define f first
#define s second
long long a[600000],used[600000],l[600000],r[600000];
priority_queue<pair<long long,long long> >q;
inline void read(long long &x){long long f=1;x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+(s-'0');s=getchar();}x*=f;
}
int main()
{     long long n,m,i,j,k;read(n),read(m);for(i=1;i<=n;i++){read(a[i]);q.push(make_pair(a[i],i));l[i]=i-1;r[i]=i+1;}long long ans=0;while(m--){while(used[q.top().s])q.pop();long long x=q.top().f,y=q.top().s;q.pop();if(x<0)break;ans+=x;a[y]=a[l[y]]+a[r[y]]-x;used[l[y]]=used[r[y]]=1;l[y]=l[l[y]];r[l[y]]=y;r[y]=r[r[y]];l[r[y]]=y;q.push(make_pair(a[y],y));}printf("%lld\n",ans);return 0;
}