洛谷 P10119 题解

$\text{[Solution]}$

首先，应该可以很明显看出来这题是一道 dp 题。

记 $f_{j,i,0/1}$ 表示在 $i$ 分钟初第 $j$ 次踱步（即第 $i$ 分钟初一定会踱步），踱步后在屋内/外的状态下，前 $(i-1)$ 分钟（为了方便转移，不包括第 $i$ 分钟）的总心情值的最大值。

（这一段话特别的拗口，没办法，语文水平不太高。大家多读几次将就一下吧。）

转移方程还是比较显然的，以 $f_{j,i,0}$ 为例：

$$f_{j,i,0}=\underset{t=1}{\overset{i-1}{\max }}\left\{f_{t,j-1,1}+\sum _{k=t}^{i-1}{b}_k+P\text{[if }i-t\le T]\right\}$$

解释一下，由于第 $i$ 分钟踱步后进入了屋内，所以踱步前应该在屋外，所以中间加的应该是在屋外的心情值。

$f_{j,i,1}$ 同理，不过中间那一项应该是在屋外的心情值。

显然，我们可以用前缀和维护中间的连续求和项。不太好办的是那个 $P$。我们不能枚举 $t$，那样时间复杂度将是 $O(N^2\times K)$，会超时。

那就分类讨论吧，对于 $i-T\le t<i$ 的每一个 $t$，是要加上这个 $P$ 的，我们发现这个转移区间长度是确定的，但是左端点会每次加 $1$。这非常非常符合单调队列优化 dp 的要求。可以用单调队列优化至平均每次转移 $O(1)$。

对于 $t<i-T$ 的区间呢？我们发现，这个转移区间只会变长，不会变短或者删除某些解，于是用一个变量就可以维护。平均每次也是 $O(1)$ 的。

因此，总时间复杂度为 $O(NK)$。

另外，为了避免 MLE，应该要用滚动数组。

注意细节，要养成良好的清空数组的习惯。其它具体看代码。

$\text{[code]}$

const int N=2e5+100;
typedef long long ll;
const ll inf=(ll)1e18;

ll sum[N][2],f[2][N][2],ans;
int q[N][2],hd[2],tl[2],n,k,t,p,T;

inline ll val(int pos,int Tim,int id){
	return f[Tim][pos][id]-sum[pos-1][id];
}

inline ll ckmax(ll &a,ll b){
	return (a=((a>b)?a:b));
}

inline int initdata(){
	for(int i=0;i<=n+2;i++)
		f[0][i][0]=f[1][i][1]=-inf;
	for(int i=0;i<=n+2;i++)
		sum[i][0]=sum[i][1]=0;
	for(int i=0;i<=n+2;i++)
		q[i][0]=q[i][1]=0;
	ans=-inf;
	
	return 0;
}//不能直接用 memset

int main(){
	read();T=read();
	while (T--){
		n=read();k=read();
		t=read();p=read();
		
		initdata();
		
		for(int i=1;i<=n;i++){
			sum[i][0]=sum[i-1][0]+read();
			sum[i][1]=sum[i-1][1]+read();
		}
		
		ans=max(sum[n][0],sum[n][1]);
		
		for(int i=1;i<=n;i++){
			f[0][i][0]=sum[i-1][0];
			f[0][i][1]=sum[i-1][1];
		}
		
		for(int j=1;j<=k;j++){
			int now=j&1,lst=now^1;
			for(int i=0;i<=n+2;i++)
				f[now][i][0]=f[now][i][1]=-inf;//记得清空
			hd[0]=hd[1]=1;tl[0]=tl[1]=0;
			
			ll max1=-inf,max0=-inf;
			
			for(int i=1;i<=n;i++){
				while (hd[0]<=tl[0]&&q[hd[0]][0]<i-t) hd[0]++;
				if (i>=j&&hd[0]<=tl[0]) f[now][i][0]=val(q[hd[0]][0],lst,1)+sum[i-1][1]+p*(j>1);
				注意这里，j=1 的时候无论如何也不能加上 p
				while (hd[0]<=tl[0]&&val(q[tl[0]][0],lst,1)<=val(i,lst,1)) tl[0]--;
				q[++tl[0]][0]=i;
				
				while (hd[1]<=tl[1]&&q[hd[1]][1]<i-t) hd[1]++;
				if (i>=j&&hd[1]<=tl[1]) f[now][i][1]=val(q[hd[1]][1],lst,0)+sum[i-1][0]+p*(j>1);
				while (hd[1]<=tl[1]&&val(q[tl[1]][1],lst,0)<=val(i,lst,0)) tl[1]--;
				q[++tl[1]][1]=i;
				
				if (i>t){
					ckmax(f[now][i][0],max1+sum[i-1][1]);
					ckmax(f[now][i][1],max0+sum[i-1][0]);
					ckmax(max1,val(i-t,lst,1));
					ckmax(max0,val(i-t,lst,0));
				}
			}
			
			for(int i=j;i<=n;i++)
				ckmax(ans,max(f[now][i][0]+sum[n][0]-sum[i-1][0],f[now][i][1]+sum[n][1]-sum[i-1][1]));
		}
		
		printf("%lld\n",ans);
	}
	
	return 0;
}