NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 G. 最大不連續和問題

作者 主題: G. 最大不連續和問題  (閱讀 453 次)

oToToT

  • 新手
  • *
  • 文章數: 5
    • 檢視個人資料
G. 最大不連續和問題
« 於: 三月 19, 2018, 02:33:49 pm »

DP即可
代碼: [選擇]
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 1000000 + 5;
const lld INF = 1LL<<60;
lld arr[N], sum[N], dp[N];

int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>arr[i];
lld cnt=0, mm = -INF;
for(int i=1;i<=n;i++){
cnt += arr[i];
mm = max(cnt,mm);
if(cnt < 0) cnt = 0;
sum[i] = mm;
}
dp[0]=-INF; dp[1]=-INF; dp[2]=-INF;
lld mx = -INF;
for(int i=3;i<=n;i++){
dp[i] = max(mx+arr[i], sum[i-2]+arr[i]);
mx = max(mx, dp[i]);
}
lld ans = -INF;
for(int i=1;i<=n;i++) ans=max(ans, dp[i]);
cout<<ans<<'\n';
return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2017高中組決賽
 G. 最大不連續和問題