題意：

給定一段長(zhǎng)為N的序列，選取其中的至多M段使這些子段和最大。

---

當(dāng)N=1000時(shí)，我們可以采用動(dòng)態(tài)規(guī)劃解法

令\(dp[i][j][k]\)代表當(dāng)前選至位置\(i\)處于第\(j\)段當(dāng)前是否選取(1選0不選)

則轉(zhuǎn)移為
\(dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0])\)
\(dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j][1])+score[i]\)

其中\(i\)的一維可以滾動(dòng)掉

Code：

#include <cstdio> #include <cstring> int max(int x,int y){return x>y?x:y;} const int N=503; const int inf=0x3f3f3f3f; int dp[N][N][2],n,k,score[N]; void init() {scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",score+i);memset(dp,-0x3f,sizeof(dp));dp[1][0][0]=0,dp[1][1][1]=score[1]; } void work() {for(int i=2;i<=n;i++)for(int j=0;j<=k;j++){dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);dp[i][j][1]=max(dp[i-1][j-1][0],dp[i-1][j][1])+score[i];}int ans=-inf;for(int i=0;i<=k;i++)ans=max(ans,max(dp[n][i][0],dp[n][i][1]));printf("%d\n",ans); } int main() {init();work();return 0; }

---

當(dāng)N=100,000時(shí)，我們可以采用貪心解法
注意到每次選取時(shí)，一段連續(xù)的正數(shù)或者連續(xù)的負(fù)數(shù)，要么我們不取選它，要么全部選走。

我們先縮個(gè)點(diǎn)，使序列變成正負(fù)數(shù)交錯(cuò)的，其中，第一項(xiàng)和最后一項(xiàng)的負(fù)數(shù)我們一定不去選擇，故舍去。

設(shè)當(dāng)前有\(k\)個(gè)正數(shù)。

則當(dāng)\(M>=k\)時(shí)，直接選取\(k\)個(gè)正數(shù)即可。

當(dāng)\(M<=k\)時(shí)，對(duì)每個(gè)正數(shù)，我們有兩種選擇，放棄它，或者跨過負(fù)數(shù)選擇它。

則當(dāng)選中一個(gè)負(fù)數(shù)\(a\)時(shí)，我們損失了\(-a\)，當(dāng)放棄一個(gè)正數(shù)\(b\)時(shí)，我們損失了\(b\)

則不管哪種情況，我們只需要找到絕對(duì)值最小的一個(gè)數(shù)，選擇它或者放棄它

采用二叉堆維護(hù)這個(gè)最小值

當(dāng)這個(gè)最小值被操作時(shí)，其實(shí)等價(jià)于新產(chǎn)生了一個(gè)權(quán)值為 它和它旁邊的兩個(gè)元素的權(quán)值和 的新元素，這時(shí)候產(chǎn)生的新數(shù)列一定會(huì)少一個(gè)正數(shù)

值得一提的是，當(dāng)?shù)谝豁?xiàng)和最后一項(xiàng)是負(fù)數(shù)的時(shí)候，不一定一定減少一個(gè)正數(shù)，所以我們根據(jù)貪心不去選擇這些點(diǎn)即可

合并元素可以采用鏈表進(jìn)行維護(hù)

Code:（實(shí)在是不好看QAQ）

#include <cstdio> #include <cstring> #include <iostream> #include <queue> #define ll long long #define P pair <ll,ll> using namespace std; const int N=1000010; ll a[N],b[N],n0,k,n,pre[N],suc[N],cnt,used[N]; ll labs(ll x){return x>0?x:-x;} void init() {scanf("%lld%lld",&n0,&k);for(int i=1;i<=n0;i++)scanf("%lld",a+i);int k=0;a[0]=-1;while(a[k]<0) k++;for(int i=k;i<=n0;i++){if(a[i]*a[i-1]>0)b[n]+=a[i];elseb[++n]=a[i];}while(n&&b[n]<0) n--;for(int i=1;i<=n;i++){pre[i]=i-1;suc[i]=i+1;}suc[0]=1;suc[n]=0; } priority_queue <P,vector <P >,greater <P > > q; P p; void work() {for(int i=1;i<=n;i++){if(b[i]>0) cnt++;p.first=labs(b[i]);p.second=i;q.push(p);}while(cnt>k){int pos=q.top().second;q.pop();if(used[pos]) continue;if(!suc[pos]&&b[pos]<0){suc[pre[pos]]=suc[pos];pre[suc[pos]]=pre[pos];continue;}if(!pre[pos]&&b[pos]<0){pre[suc[pos]]=pre[pos];suc[pre[pos]]=suc[pos];continue;}used[pre[pos]]=used[suc[pos]]=1;b[pos]+=b[pre[pos]]+b[suc[pos]];cnt--;if(pre[pos]){pre[pos]=pre[pre[pos]];suc[pre[pos]]=pos;}if(suc[pos]){suc[pos]=suc[suc[pos]];pre[suc[pos]]=pos;}p.first=labs(b[pos]),p.second=pos;q.push(p);}int now=suc[0];ll ans=0;while(now){if(b[now]>0) ans+=b[now];now=suc[now];}printf("%lld\n",ans); } int main() {init();work();return 0; }

---

當(dāng)N=1,000,000時(shí)，我們可以將算法近似優(yōu)化到\(O(N)\)

具體大家可以參考出題人的題解

我在這里解釋一下這個(gè)近似，原題解沒有說道找到第\(k\)值的問題

主要就是利用基于快速排序思想的STL函數(shù)\(nth\_element\)，可以在近似\(O(n)\)的復(fù)雜度找到第\(k\)值

關(guān)于第k值

代碼我沒寫，感覺不太好寫

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

總結(jié)

以上是生活随笔為你收集整理的洛谷 P2389 电脑班的裁员 解题报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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