自动搬运

查看原文

来自洛谷，原作者为

	Noby_Glds be serious

搬运于2025-08-24 22:54:52，当前版本为作者最后更新于2024-02-01 22:11:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先对 $a,b$ 做前缀和，分别表示为 $s_{0},s_1$。

设 $f_{i,k,op}$ 表示对于前 $i$ 个位置，强制在 $i+1$ 分钟初踱步，总共踱步 $k$ 次，且第 $i$ 分钟在屋内（$op=0$）或屋外（$op=1$）的最大答案。

显然我们有以下转移方程：

$$f_{i,k,op}=\max_{j=k-1}^{i-1}{f_{j,k-1,1-op}}+s_{i,op}-s_{j,op}+[i-j\leq T]P $$

移项可得：

$$f_{i,k,op}-s_{i,op}=\max_{j=k-1}^{i-1}{f_{j,k-1,1-op}}-s_{j,op}+[i-j\leq T]P $$

滚动数组滚掉一维：

$$g_{i,op}-s_{i,op}=\max_{j=k-1}^{i-1}f_{j,1-op}-s_{j,op}+[i-j\leq T]P $$

分情况讨论：

$i-j\leq T$

此时转移区间的范围是 $[i-T,i-1]$，且联系到区间求最值，我们很容易想到单调队列优化，别忘了把答案加上 $P$。

$i-j>T$

转移区间为 $[k-1,i-T-1]$，注意到左端点固定，右端点递增，只需要开一个变量维护最大值。

最后，$op$ 有两个取值，记得要做两次转移。

#include<bits/stdc++.h>
#define int long long
#define N 200010
using namespace std;
int id,T,n,m,t,p;
int f[N][2],s[N][2],g[N][2],q[N];
int get(int x,int y){return f[x][y^1]-s[x][y];}
void work(int pos,int op){
	int now=-1e18,l=1,r=1;
	q[1]=pos-1;
	for(int i=pos;i<=n;i++){
		if(i-t-1>=pos-1) now=max(now,get(i-t-1,op));
		while(l<=r&&q[l]<i-t) l++;
		g[i][op]=max(now,get(q[l],op)+p)+s[i][op];
		while(l<=r&&get(i,op)>=get(q[r],op)) r--;
		q[++r]=i;
	}
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>id>>T;
	while(T--){
		cin>>n>>m>>t>>p;
		for(int i=1;i<=n;i++){
			cin>>s[i][0]>>s[i][1];
			s[i][0]+=s[i-1][0],s[i][1]+=s[i-1][1];
			f[i][0]=s[i][0],f[i][1]=s[i][1];
		} 
		int ans=max(s[n][0],s[n][1]);//不踱步
		for(int i=1;i<n;i++) ans=max(ans,max(f[i][0]+s[n][1]-s[i][1],f[i][1]+s[n][0]-s[i][0]));//一次踱步
		for(int pos=2;pos<=m;pos++){
			work(pos,0),work(pos,1);
			for(int i=pos;i<n;i++){
				f[i][0]=g[i][0],f[i][1]=g[i][1];
				ans=max(ans,max(f[i][0]+s[n][1]-s[i][1],f[i][1]+s[n][0]-s[i][0]));
			} 
		}
		cout<<ans<<endl;
	}
	return 0;
}