[luogu] AT2264 [AGC008B] Contiguous Repainting 前缀和

前言

传送门 :

题意

给定 n n n, k k k和一个 a [ ] a[] a[]

一开始这个数组都是白色的,我们可以令任意个连续的 k k k区间进行染色,黑->白,白->黑

最后使得黑色的格子和最大

思路

我们会发现 只有最后的那个长度为 k k k的区间以外的所有格子,都是可以自由染色的

因此我么可以两侧区间涂色,然后慢慢的往中间挪

Mycode

const int N = 1e5+10;
int a[N],n,k;
ll pre[N],suf[N],sum[N];

void solve(){
	cin>>n>>k;
	
	for(int i=1;i>a[i];
	
	for(int i=1;i