CF115DBeautiful Array

　　題目大意：給一個有n個元素的a數組，可以選擇其中一個區間的所有數都乘上x，也可以不選，求最大子序列和。

　　如果沒有前面的操作，就是只求最大子序列和，我們都知道就一個貪心的思路，當目前序列的和<0了，我們就當它為0，因為它對后面的序列只有負的貢獻，完全不會使和增大，只會使和減少。所以我們從左往右，和從右往左，分別處理出沒有乘x的最大子序列和maxl和maxr，這樣的話，如果我們在區間[l,r]內乘x，那么相應的答案就是(sum[r]-sum[l-1])*x+maxr[r+1]+maxl[l-1],emmm那天晚上我就推到了這，后面怎么枚舉區間就不懂了，寫了個尺取，但很明顯不對，因為沒有根據去調整區間。看了我們qdcxk的博客后領悟，還是一種貪心的思想。我們把前面的答案轉化成sum[r]*x+maxr[r+1]-(sum[l-1]*x-maxl[l-1]),這樣的話

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 typedef long long ll; 5 int a[301108]; 6 ll sum[301108],maxl[301108],maxr[301108]; 7 int main() 8 { 9 int n,x,y; 10 scanf("%d%d",&n,&x); 11 for(int i=1;i<=n;i++) 12 { 13 scanf("%d",&a[i]); 14 sum[i]=sum[i-1]+a[i]; 15 } 16 for(int i=1;i<=n;i++) 17 { 18 maxl[i]=maxl[i-1]+a[i]; 19 if(maxl[i]<0) 20 maxl[i]=0; 21 } 22 for(int i=n;i>=1;i--) 23 { 24 maxr[i]=maxr[i+1]+a[i]; 25 if(maxr[i]<0) 26 maxr[i]=0; 27 } 28 ll ans=0,minl=0; 29 for(int i=1;i<=n;i++) 30 { 31 minl=min(minl,sum[i]*1ll*x-maxl[i]);//先更新minl,就把不選的情況也包含了 32 ans=max(ans,maxr[i+1]+sum[i]*1ll*x-minl); 33 } 34 printf("%lld\n",ans); 35 return 0; 36 } 我全都要

qdcxk還有個dp的做法，先掛上一發k神博客mmk27，沒看懂，等k神給我講明白了再更。

轉載于:https://www.cnblogs.com/LMCC1108/p/10761228.html

總結

以上是生活随笔為你收集整理的CF1155D Beautiful Array 贪心,dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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