来自一本通5.5 例3luogu

好习惯，先看数据范围

#### 数据范围与提示

对于全部数据，$1\leq N\leq 10^5,0\leq E_i \leq 10^9$ 。

那么要用long long是显然的了。N的大小让人怀疑有log，但是其实没有

可能是考虑到deque巨大的常数吧反正我不喜欢用STL

不多说，直接上代码。边看边讲。

part1 朴素DP

前置

max函数不能写const ll&，可能是因为临时变量的问题。

#include<cstdio>
#define ll long long
int n,k;
ll max(const ll a,const ll b){return a>b?a:b;}
ll maxx[100005],e[100005],sum[100005],max2[100005];

main函数

前缀和便于查询连续的奶牛效率值之和

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%lld",e+i),sum[i]=sum[i-1]+e[i];
	//*/
	if(n*k<=1e7){part2();return 0;}
	//*/
	part3();
	return 0;
}

part1·1

设$f_{i,j}$表示前前i头奶牛, 有j头奶牛（包括第i頭）与i连在一起，所能取得的最大效率

$maxx_i$表示考虑了前i头奶牛所取得的最大效率

for(int i=1;i<=n;++i){//前i头奶牛, 有多少奶牛（包括第i頭）与i连在一起 
	F[i][0]=maxx[i-1];//该位不选奶牛的话，上一位方案随意，不会受到k限制
	for(int j=1;j<=i&&j<=k;++j){
		F[i][j]=max(F[i][j],maxx[i-j-1]+sum[i]-sum[i-j]);
		maxx[i]=max(maxx[i],F[i][j]);//记下前i头奶牛的最大效率值便于查询
	}
}
printf("%lld",maxx[n]);

part1·2

发现上面输出的是maxx数组而非F数组，直接干掉F数组

for(int i=1;i<=n;++i){//上面的优化成这样 
	//F[i][0]=maxx[i-1];
	for(int j=1;j<i&&j<=k;++j){
		maxx[i]=max(maxx[i],maxx[i-j-1]+sum[i]-sum[i-j]);
	}
	if(i<=k)maxx[i]=max(maxx[i],sum[i]);//其实就是sum[i] 
}

至此能得70分，注意main函数里加上一句：(暴力得省一)

if(n*k<=1e7){part();return 0;}

因为$ n*k $的复杂度，所以保守估计$ 10^7 $，结果能得70分

开个O2，把限度放大一点，能得貌似80。不过我不敢这么浪

网上到处都说60分，@houyq的代码也是60分，由此可见该冒险的时候可以试试

part2

上面maxx数组只有1维，且后面的状态都是由前面的状态转移而来

看出来这是一道线性DP所以直接想到单调队列（不是）

part2·1

尝试继续优化，定义新数组把状态记下来免得多次计算（卡常级别的优化）

其实这么做的动机是因为，对于每个i，+sum[i]是不变的，maxx[i]一开始是0

变的东西只有这个[i-j+1]和[i-j]，他俩随着j变而变

所以单独开个max2[]把两个东西合并了记下来，

max2[]没有什么实际意义，是为了分离变量和“不变暂时不变的量”而创造的新量

for(int i=1;i<=n;++i){//上面的“优化”成这样 
	for(int j=1;j<=i&&j<=k;++j){
		maxx[i]=max(maxx[i],max2[i-j]+sum[i]);
	}
	if(i<=k)maxx[i]=sum[i];
	max2[i]=maxx[i-1]-sum[i];
	//定义新数组, 因为第19行的i-j-1和i-j总是差1 
}

注意到第19行：

18	for(int j=1;j<i&&j<=k;++j){
19      maxx[i]=max(maxx[i],maxx[i-j-1]+sum[i]-sum[i-j]);
20	}

于是到了下一个要点：

part2·2

发现max()操作每次都有一个 +sum[i] 的操作，不顺眼，干掉

第二重循环需要倒着来，不顺眼，正着来

......

其实是因为发现是个滑动窗口查询区间最大值而改的

还有这一行 if(i<=k)maxx[i]=sum[i]; 不好，很复杂，抽出来

变成了这个样子

for(int i=1;i<=k;++i)
maxx[i]=sum[i],max2[i]=maxx[i-1]-sum[i];
for(int i=k+1;i<=n;++i){
	for(int j=1;j<=k;++j){//i-j∈[i-k,i-1]
		maxx[i]=max(maxx[i],max2[i-j]+sum[i]);
	}
	max2[i]=maxx[i-1]-sum[i];
}

至此，复杂度依然没变（常数大大减小，但是没太大用处）

$ However,$这给我们理解下面的代码带来了极大的方便

正片：单调队列优化

part3·1 要讲了

欸还没讲呢

先用个Max进一步铺垫一下，更直观

for(int i=1;i<=k;++i)
maxx[i]=sum[i],max2[i]=maxx[i-1]-sum[i];
for(int i=k+1,Max,j;i<=n;++i){//上面的优化成这样 
	for(j=i-k,Max=0;j<=i-1;++j){//i-j∈[i-k,i-1]
		if(Max<max2[j])Max=max2[j];
	}
	maxx[i]=Max+sum[i];
	max2[i]=maxx[i-1]-sum[i];//定义新数组 
}

我们写了一行注释：

//i-j∈[i-k,i-1]

1和k是常数。

我们想到，这个区间只会随着i的增加向右移动

而我们要的是区间内部的最大值

那么这显然是个滑动窗口问题

上板子，单调队列

ll dq[200005];int qh=1,qt=2;//deque::[qh,qt)
for(int i=1;i<=k;++i){
    maxx[i]=sum[i];
    const ll tmp=maxx[i-1]-sum[i];
    while(qh<=qt&&tmp>dq[qt])qt--;//单调性维护 
    dq[++qt]=tmp;
}
for(int i=k+1;i<=n;++i){//上面的优化成这样 
    maxx[i]=dq[qh]+sum[i];
    const ll tmp=maxx[i-1]-sum[i];
    while(qh<=qt&&tmp>dq[qt])qt--;//单调性维护 
    dq[++qt]=tmp;
    while(qh<=qt&&qh<=i-k)qh++;//时效性维护 
}

上面的代码看起来可以AC并不可以AC但是我并不打算用再改下去了

因为我枯了

因为它会给选手带来极大的困惑并且它能通过小样例

我们推荐这种写法，即让队列记录编号而不是队首直接充当编号。

因为队列是一个容器，它的head和tail应该是private，对外不可见的，应该是没有实际意义的，面向过程的一个中间量，而容器本身盛放的东西才有意义

因此我写的代码中的qh做编号直接与i-k比较是一种极其耗费脑力的写法

不如用STL做法或者如下（手写的deque，详见下面的AC代码）：

for(int i=1;i<=k;++i){
	maxx[i]=sum[i];
	max2[i]=maxx[i-1]-sum[i];
	while(!dq.empty()&&max2[i]>max2[dq.tail()])dq.popt();//单调性维护 
	dq.push(i);
}
for(int i=k+1;i<=n;++i){//上面的优化成这样 
	maxx[i]=max2[dq.head()]+sum[i];
	max2[i]=maxx[i-1]-sum[i];
	while(!dq.empty()&&max2[i]>max2[dq.tail()])dq.popt();//单调性维护 
	dq.push(i);
	while(!dq.empty()&&dq.head()<=i-k)dq.poph();//时效性维护 
}

非常符合C++面向对象的精髓所在（C才是面向过程）

还有许多其他做法，比如记录谁不选。因为我们要的是思维难度稍小一点的做法，所以不再赘述。（一上来就取反谁受得了啊）

总结：DP多练啊。不练，会的东西看不出来，也掌握不了

附上AC代码，手写的deque，常数小，小至近STL的 $\frac{1}{4}$，真不错：

#include<cstdio>
#define ll long long
int n,k;
ll max(ll a,ll b){return a>b?a:b;}
ll maxx[100005],e[100005],sum[100005],max2[100005];
void part(){
	/*/
	for(int i=1;i<=n;++i){//前i头奶牛, 该位时有多少奶牛连在一起 
		F[i][0]=maxx[i-1];
		for(int j=1;j<=i&&j<=k;++j){
			F[i][j]=max(F[i][j],maxx[i-j-1]+sum[i]-sum[i-j]);
			maxx[i]=max(maxx[i],F[i][j]);
		}
	}//*/
	for(int i=1;i<=n;++i){//上面的优化成这样 
		//F[i][0]=maxx[i-1];
		for(int j=1;j<i&&j<=k;++j){
			maxx[i]=max(maxx[i],maxx[i-j-1]+sum[i]-sum[i-j]);
		}
		if(i<=k)maxx[i]=max(maxx[i],sum[i]);//其实就是sum[i] 
	}
	//for(int i=1;i<=n;++i)printf("%lld ",maxx[i]);
	printf("%lld",maxx[n]);
}
void part2(){
	/*/ 
	for(int i=1;i<=n;++i){//上面的优化成这样 
		for(int j=1;j<=i&&j<=k;++j){
			maxx[i]=max(maxx[i],max2[i-j]+sum[i]);
		}
		if(i<=k)maxx[i]=sum[i];
		max2[i]=maxx[i-1]-sum[i];
		//定义新数组, 因为第19行的i-j-1和i-j总是差1 
	}//*/
	//*/
	for(int i=1;i<=k;++i)
	maxx[i]=sum[i],max2[i]=maxx[i-1]-sum[i];
	for(int i=k+1;i<=n;++i){//上面的优化成这样 
		for(int j=1;j<=k;++j){//i-j∈[i-k,i-1]
			maxx[i]=max(maxx[i],max2[i-j]+sum[i]);
		}
		max2[i]=maxx[i-1]-sum[i];//定义新数组 
	}//*/
	printf("%lld",maxx[n]);
}
struct deque{
	//deque::[qh,qt)
	private:int qh,qt,dq[100005];
	public:deque(){qh=qt=0;} 
	bool empty(){return qh>=qt;}
	int head(){return dq[qh];}
	int tail(){return dq[qt-1];}
	void poph(){qh++;}
	void popt(){qt--;}
	void push(const int& x){dq[qt++]=x;} 
}dq;
void part3(){
	/*/
	for(int i=1;i<=k;++i)
	maxx[i]=sum[i],max2[i]=maxx[i-1]-sum[i];
	for(int i=k+1,Max,j;i<=n;++i){//上面的优化成这样 
		for(j=i-k,Max=0;j<=i-1;++j){//i-j∈[i-k,i-1]
			if(Max<max2[j])Max=max2[j];
		}
		maxx[i]=Max+sum[i];
		max2[i]=maxx[i-1]-sum[i];//定义新数组 
	}//*/
	for(int i=1;i<=k;++i){
		maxx[i]=sum[i];
		max2[i]=maxx[i-1]-sum[i];
		while(!dq.empty()&&max2[i]>max2[dq.tail()])dq.popt();//单调性维护 
		dq.push(i);
	}
	for(int i=k+1;i<=n;++i){//上面的优化成这样 
		maxx[i]=max2[dq.head()]+sum[i];
		max2[i]=maxx[i-1]-sum[i];
		while(!dq.empty()&&max2[i]>max2[dq.tail()])dq.popt();//单调性维护 
		dq.push(i);
		while(!dq.empty()&&dq.head()<=i-k)dq.poph();//时效性维护 
	}
	printf("%lld",maxx[n]);
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)scanf("%lld",e+i),sum[i]=sum[i-1]+e[i];
	//*/
	if(n*k<=1e7){part2();return 0;}//部分分保底
	//*/
	part3();
	return 0;
}