題目描述

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

輸入輸出格式

輸入格式：

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

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

輸出格式：

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

輸入輸出樣例

輸入樣例#1：? 6 3 100 1 -1 100 1 -1 輸出樣例#1：? 200

說明

對于20%的數據，n<=20。

對于50%的數據，n<=6000。

對于100%的數據，n<=500000，k<=n/2,在一個地方種樹獲利的絕對值在1000000以內。

?

Solution:

　　本題的二叉堆的做法實在是太巧妙了！！！

　　首先，我打了一個普通的$DP$，期望得分$50$，很容易想到狀態$f[i][j],\;i\in[1,n],\;j\in[1,k]$表示前$i$個位置中了$j$棵樹的最大獲利，則由題目限制條件不難想到狀態轉移方程：$f[i][j]=max(f[i-1][j],f[i-2][j-1]+a[i])$，注意下邊界和初始狀態就有$50$分了。時間空間復雜度都是$O(n^2)$，顯然不行。

　　此時想了各種奇技淫巧，依然沒用。。。還是默默的看了下題解，驚嘆于本題的二叉堆做法：

　　我們先進行小規模枚舉： $k=1$時，顯然取$n$個數中取最大的即可（暫不考慮全負的情況）。設最大的數是$a[i]$。

　　$k=2$時，則有兩種可能：1、另取一個與$a[i]$不相鄰的$a[j]$。2、取$a[i-1]$和$a[i+1]$。

　　我們可以發現：如果$k=1$時最優解為$a[i]$，那么我們便可以把$a[i-1]$和$a[i+1]$進行合并，因為它們要么同時被選，要么同時落選（證明不難，請自行解決）。而且，我們還注意到：當選了$a[i-1]$和$a[i+1]$時，獲利便增加了$a[i-1]+a[i+1]-a[i]$。所以當$a[i]$被選時，我們就可以刪去$a[i-1]$和$a[i+1]$，并把$a[i]$改成$a[i-1]+a[i+1]-a[i]$（即使為負也沒問題，因為下次不會選它，而若為正則等同于選了$a[i-1]$和$a[i+1]$），重新找最大的。

　　每次找的都是最大的數，我們便可以使用堆進行操作，直到堆中最大值小于等于$0$或取出$k$個數后停止。復雜度$O(nlogn)$。

?

1、先安利一下自己$DP$的代碼：

#include<bits/stdc++.h> #define il inline #define ll long long using namespace std; const int N=10005; ll n,k,f[N][5000],ans=-100000000; int a[N]; il ll gi(){ll a=0;char x=getchar();bool f=0;while((x<'0'||x>'9')&&x!='-')x=getchar();if(x=='-')x=getchar(),f=1;while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();return f?-a:a; } int main(){n=gi(),k=gi();for(int i=1;i<=n;i++)a[i]=gi();for(int i=1;i<=n;i++)for(int j=1;j<=k;j++)f[i][j]=-100000000;f[1][1]=a[1];for(int i=2;i<=n;i++)for(int j=1;j<=k&&j<=i;j++){if(i-2>0)f[i][j]=max(f[i-1][j],f[i-2][j-1]+a[i]);else f[i][j]=f[i-1][j];ans=max(f[i][j],ans);}cout<<ans;return 0; }

?

?

2、再發一波正解代碼：

#include<bits/stdc++.h> #define il inline #define ll long long using namespace std; const int N=500005; int n,k; ll ans,tot,a[N],l[N],r[N],pos; struct node{int v,id;bool operator < (const node a)const {return v<a.v;} }tmp; priority_queue<node>q; bool vis[N]; il ll gi(){ll a=0;char x=getchar();bool f=0;while((x<'0'||x>'9')&&x!='-')x=getchar();if(x=='-')x=getchar(),f=1;while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();return f?-a:a; } int main(){n=gi(),k=gi();for(int i=1;i<=n;i++){tmp.v=gi(),tmp.id=i;q.push(tmp);l[i]=i-1;r[i]=i+1;a[i]=tmp.v;}r[0]=1,l[n+1]=n;while(k--){while(vis[q.top().id])q.pop();tmp=q.top();q.pop();if(tmp.v<0)break;ans+=tmp.v;pos=tmp.id;a[pos]=a[l[pos]]+a[r[pos]]-a[pos];tmp.v=a[pos];vis[l[pos]]=vis[r[pos]]=1;l[pos]=l[l[pos]],r[l[pos]]=pos;r[pos]=r[r[pos]],l[r[pos]]=pos;q.push(tmp);}cout<<ans;return 0; }

?

?

轉載于:https://www.cnblogs.com/five20/p/8955018.html

總結

以上是生活随笔為你收集整理的P1484 种树的全部內容，希望文章能夠幫你解決所遇到的問題。

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