本文主要是介绍Contiguous Repainting(贪心+思维)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
5616: Contiguous Repainting
时间限制: 2 Sec 内存限制: 256 MB提交: 70 解决: 23
[ 提交][ 状态][ 讨论版][命题人: 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
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
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.
来源
AtCoder Grand Contest 008
题意：选择长度为K的区间涂颜色，可以重复涂，每次可以涂白或者黑，问 操作多次后黑颜色方块的值的总和最大是多少。
题解：每次枚举区间的时候都是最后一次的k区间内不可控，那么可直接选择，最后一次的k全选或全不选，每次枚举最后的k区间的位置，然后将外面的正数求和，再将k区间内的数加起来看是正还是负。
#include<stdio.h>
#include <algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#define INF 0x3f3f3f3f
#define gcd(a,b) __gcd(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=1e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}ll a[100005];
int main()
{int n,k;cin>>n>>k;ll sum=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);if(a[i]>0) sum+=a[i];}ll temp=0,ans=0;for(int i=1;i<=k;i++){temp+=a[i];if(a[i]>0) sum-=a[i];}ans=max(ans,max(temp+sum,sum));for(int i=2;i<=n-k+1;i++){temp-=a[i-1];temp+=a[k+i-1];if(a[i-1]>0)sum+=a[i-1];if(a[i+k-1]>0)sum-=a[i+k-1];ans=max(ans,max(temp+sum,sum));}printf("%lld\n",ans);
}
这篇关于Contiguous Repainting(贪心+思维)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
