Contiguous Repainting
题目描述
There are N squares aligned in a row. The i-th square from the left contains an integer ai.
Initially, all the squares are white. Snuke will perform the following operation some number of times:
Select K consecutive squares. Then, paint all of them white, or paint all of them black. Here, the colors of the squares are overwritten.
After Snuke finishes performing the operation, the score will be calculated as the sum of the integers contained in the black squares. Find the maximum possible score.
Constraints
1≤N≤10 5
1≤K≤N
ai is an integer.
|ai|≤10 9
Initially, all the squares are white. Snuke will perform the following operation some number of times:
Select K consecutive squares. Then, paint all of them white, or paint all of them black. Here, the colors of the squares are overwritten.
After Snuke finishes performing the operation, the score will be calculated as the sum of the integers contained in the black squares. Find the maximum possible score.
Constraints
1≤N≤10 5
1≤K≤N
ai is an integer.
|ai|≤10 9
输入
The input is given from Standard Input in the following format:
N K
a 1 a 2 … a N
N K
a 1 a 2 … a N
输出
Print the maximum possible score.
样例输入
5 3
-10 10 -10 10 -10
样例输出
10
提示
Paint the following squares black: the second, third and fourth squares from the left.Contiguous Repainting
除了最后一次刷，再这一k段序列的其他正数都可以取到
把这k段序列当作刷白的中转站，反正就算黑了几个再把这k个刷白。
最后再考虑这k个要不要刷黑
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=1e5+5; ll s[maxn],a[maxn]; int main(){ int n,k,t; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>t; s[i]=s[i-1]+t; a[i]=a[i-1]; if(t>0) a[i]+=t; } ll ans=0; for(int i=1;i+k-1<=n;i++){ ll sum=a[n]-(a[i+k-1]-a[i-1]); if(s[i+k-1]-s[i-1]>0) sum+=s[i+k-1]-s[i-1]; ans=max(ans,sum); } cout<<ans<<endl; return 0; }
投递保时捷等公司8个岗位 >
点点互动一面16人在聊
