Contiguous Repainting

時(shí)間限制:?2 Sec??內(nèi)存限制:?256 MB
提交:?69??解決:?22
[提交][狀態(tài)][討論版][命題人:admin]

題目描述

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≤105
1≤K≤N
ai is an integer.
|ai|≤109

輸入

The input is given from Standard Input in the following format:

N K
a1?a2?… aN

輸出

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.

來(lái)源

AtCoder?Grand?Contest?008?

[題意]

? ? 選擇K 連續(xù) 涂顏色，可以重復(fù)涂，每次可以涂白或者黑，問 操作玩完后黑色快的總和最大是多少；

[思路]

? ? 可以發(fā)現(xiàn)，經(jīng)過nk次操作后最后一次k范圍是不可以控的，K外面，是可以將負(fù)數(shù)涂成白色，只保留正數(shù)黑色；

? ? 兩次前綴和， 跑連續(xù)的k 移動(dòng)， 取最大， 類似咸魚翻身那道題

【code】

#include <iostream> #include <bits/stdc++.h>typedef long long ll;const int MAXN=1e5+5; typedef long long ll; const int INF = 0x3f3f3f3f; using namespace std;ll a[MAXN]; ll sum[MAXN]; ll sum_int[MAXN]; int main() {int n,k;cin>>n>>k;memset(sum,0,sizeof(sum));memset(sum_int,0,sizeof(sum_int));for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];if(a[i]>0) sum_int[i]=sum_int[i-1]+a[i];else sum_int[i]=sum_int[i-1];}ll ans=-INF;for(int i=1;i<=(n-k+1);i++){ll res=0;int j=i+k-1;if( sum[j]-sum[i-1] >0) res+= sum[j]-sum[i-1];res+= sum_int[i-1]-sum[0];res+= sum_int[n]-sum_int[j];ans=max(ans,res);}cout<<ans<<endl;return 0; }

123

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

總結(jié)

以上是生活随笔為你收集整理的AtCoder Grand Contest 008: Contiguous Repainting（思维)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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