題目連結
點我吧
題目大意
給你一個長度為n的序列,先手先選擇一個區間[L,R], 這個區間裡面的數字, 讓後手選擇一個删掉。
然後計算剩餘的R-L個數字的和sum(如果R-L等于0,認為和是0)。
後手總是想讓這個sum的值比較低,是以它總是會選擇最大的那個數字删掉。
現在讓你幫先手選擇一個區間,使得這個區間在被後手删掉一個數字之後, 剩餘的和最大。
題解
這道題, 如果沒有删掉一個數字這個操作的話,就是一個 最大連續和 問題。
不熟悉這個問題的可以看看我 另外一篇文章。
大家可能都注意到了, a數組中每個元素最大都隻是30。
是以,我們可以先枚舉一下最後我們選擇的區間裡面的最大值ma是多少。
然後,将原數組做一個改動, 把數組當中所有 大于ma的值全都改成負無窮 (其他的保持不變)。
然後在這個改動後的數組裡面做最大連續子序列問題,因為比ma大的都變成負無窮了,是以肯定最後
選出來的區間沒有大于ma的數字, 這樣算出來的 最大連續和減去這個ma 就是最大值為ma的時候,問題的一個可能答案了。
但是大家可能會覺得,那如果選出來的區間中 沒有ma這個數字(裡面的數字都比ma小)怎麼辦? 其實這種情況下,我們因為枚舉了
所有的最大值,是以在 之前的枚舉中 肯定會有一次 枚舉到 了這個區間的最大值的。
總結
挺好的一個思路吧, 枚舉沖突點(最大值)是多少, 因為這個關鍵的地方被确定了,使得問題被簡化(或者說分解成很多個簡單的步驟)
題解
#include<bits/stdc++.h>
#define ll long long
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%I64d",&x)
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
using namespace std;
const int N = 1e5;
int n;
int a[N+10];
int main(){
#ifdef LOCAL_DEFINE
freopen("D:\\rush.txt","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >> n;
rep1(i,1,n){
cin >> a[i];
}
int ans = 0;
rep1(i,1,30){
int cur = 0;
rep1(j,1,n){
if (a[j]>i){
cur = 0;
}else{
cur = cur + a[j];
ans = max(ans,cur-i);
if (cur<0) cur = 0;
}
}
}
cout<<ans<<endl;
return 0;
}