自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:48:56，当前版本为作者最后更新于2023-08-05 19:52:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

写一个 dp 做法。

首先有一个很暴力的 dp，设 $dp_{i,j}$ 表示算完前 $i$ 个，从 $i$ 移到 $i+1$ 的个数大于等于 $j$ 个然后转移即可。

尝试直接维护这个 dp，首先我们把 $x_i=1$ 的段合并在一起，也就是说如果能通过 $x_i=1$ 一直往后移到比当前位置大的位置，那么就移。发现这样子之后 $c_i$ 不为 $0$ 的位置一定在段内的 $v_i$ 的后缀最大值处。

接下来考虑 dp 的时候我们在干什么，设 $cost_{i,k}$ 为第 $i$ 段的这些 $c_i$ 选 $k$ 个要往后移的最大贡献，$val_i$ 为第 $i$ 段的 $v$ 的最大值。那么转移是先枚举从 $i-1$ 段移过来个数 $j$，然后枚举这一段要往后移的个数 $k$，有 $dp_{i,\lfloor\frac{j+k}{x_i}\rfloor}=\max(dp_{i,\lfloor\frac{j+k}{x_i}\rfloor},dp_{i-1,j}+cost_{i,k})$，然后 $dp_{i,j}=\max(dp_{i,j},dp_{i,j+1}+v_{i+1})$。

首先可以发现 $cost_{i}$ 是一个上凸壳，所以每次的转移的第一步是一个闵可夫斯基和，可以在两个凸壳大小的和时间内完成。

接下来要做的是将坐标除以这一段最右点的 $x_i$，这个也可以在凸壳大小内完成。然后还有一步是 $dp_{i,j}=\max(dp_{i,j},dp_{i,j+1}+v_{i+1})$，这一步相当于 pop 掉凸壳前面一部分斜率大于 $v_{i+1}$ 的点，直接 pop 就行。

考虑这个做法的复杂度，除以 $x_i$ 的时候凸包上每个点的横坐标至少除以二。所以凸包大小总和大概是 $n\log v$ 级别，时间复杂度即为 $O(n\log v)$。

// Problem: T351677 「RiOI-2」change
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T351677?contestId=122187
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll __int128
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
#define N 200005
using namespace std;
inline char gc(){static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int n,a[N],b[N],x[N],suf[N];
bitset<10000005>vis;
struct node
{
	vector<int>x,y;
	node()
	{
		poly().swap(x),poly().swap(y);
	}
	void ins(int a,int b)
	{
		while (x.size()>0&&a==x.back()&&b>=y.back()) x.pop_back(),y.pop_back();
		if (x.size()>0&&a==x.back()&&b<y.back()) return;
		x.push_back(a);
		y.push_back(b);
	}
	void add(int k)
	{
		int l=0;
		int mx=0;
		for (int i=1;i<x.size();i++)
		{
			mx=max(mx,y[i]+x[i]*k);
			if ((y[i]-y[i-1])/(x[i]-x[i-1])>=-k) 
			{
				l=i;
			}
		}
		if (l==0) return;
		poly xx,yy;
		xx.push_back(0);yy.push_back(mx);
		for (int i=l;i<x.size();i++)
			xx.push_back(x[i]),yy.push_back(y[i]);
		x.swap(xx);
		y.swap(yy);
	}
	void selfclr()
	{
		for (int i=0;i<x.size();i++) vis[i]=0;
		int t=0;
		for (int i=1;i+1<x.size();i++)
		{
			if ((y[i]-y[i-1])*(x[i+1]-x[i])==(y[i+1]-y[i])*(x[i]-x[i-1]))
				vis[i]=1,t=1;
		}
		if (!t) return;
		poly xx,yy;
		for (int i=0;i<x.size();i++)
			if (!vis[i])
				xx.push_back(x[i]),yy.push_back(y[i]);
		x.swap(xx);
		y.swap(yy);
	}
};
pa all[10000005];
int cnt;
node merge(node x,node y)
{
	cnt=0;
	for (int i=1;i<x.x.size();i++)
	{
		all[++cnt]=mp(x.x[i]-x.x[i-1],x.y[i]-x.y[i-1]);
	}
	for (int i=1;i<y.x.size();i++)
	{
		all[++cnt]=mp(y.x[i]-y.x[i-1],y.y[i]-y.y[i-1]);
	}
	node res;
	res.ins(0,x.y[0]+y.y[0]);
	sort(all+1,all+cnt+1,[&](pa x,pa y)
	{
		return x.se*y.fi>y.se*x.fi;
	});
	for (int i=1;i<=cnt;i++)
		res.ins(res.x.back()+all[i].fi,res.y.back()+all[i].se);
	return res;
}
void outp(node x)
{
	for (int i=0;i<x.x.size();i++)
		writesp(x.x[i]),writeln(x.y[i]);
	puts("");
}
void BellaKira()
{
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=n;i++) b[i]=read();
	node dp;
	dp.x.push_back(0);
	dp.y.push_back(0);
	node st=dp;
	for (int i=1;i<n;i++) x[i]=read();
	x[n]=1;
	suf[n+1]=-1;
	for (int i=n;i>=1;i--)
	{
		suf[i]=a[i];
		if (x[i]==1) suf[i]=max(suf[i],suf[i+1]);
	}
	for (int i=1;i<n;i++)
	{
		if (x[i]==1&&suf[i+1]>=suf[i]) b[i+1]+=b[i],b[i]=0;
	}
	for (int l=1;l<=n;l++)
	{
		int r=l;
		while (r<n&&x[r]==1) r++;
		node nw=st;
		int sum=0;
		for (int i=r;i>=l;i--) sum+=a[i]*b[i];
		nw.y[0]=sum;
		for (int i=r;i>=l;i--)
			if (b[i])
			{
				nw.ins(nw.x.back()+b[i],sum-a[i]*b[i]);
				sum-=a[i]*b[i];
			}
		dp.add(suf[l]);
		nw=merge(dp,nw);
		if (r==n) 
		{
			dp=nw;
			break;
		}
		dp=node();
		dp.ins(0,nw.y[0]);
		for (int i=1;i<nw.x.size();i++)
		{
			{
				if (nw.x[i]/x[r]!=nw.x[i-1]/x[r])
				{
					dp.ins(nw.x[i]/x[r],nw.y[i]-(nw.y[i]-nw.y[i-1])*(nw.x[i]%x[r])/(nw.x[i]-nw.x[i-1]));
				}
			}
			dp.ins(nw.x[i]/x[r],nw.y[i]);
			if (i+1<nw.x.size())
			{
				if (nw.x[i+1]/x[r]!=nw.x[i]/x[r])
				{
					dp.ins(nw.x[i]/x[r]+1,nw.y[i]+(x[r]-nw.x[i]%x[r])*(nw.y[i+1]-nw.y[i])/(nw.x[i+1]-nw.x[i]));
				}
			}
		}
		dp.selfclr();
		l=r;
	}
	writeln(dp.y[0]%mod);
		
}
signed main()
{
	int id=read();
	int T=read();
	while (T--)
	{
		BellaKira();
	}
}