P1070 [NOIP2009 普及组] 道路游戏

pengchujie / 2023-08-26 / 原文

传送门

思考最朴素做法
\(f_{i,j,p}\)表示在第\(i\)个时刻终点为\(j\)且机器人走了\(p\)步获得的最大金币数，则有：

\[f_{i,j,p}=r_{w(j-1),i}+\begin{cases}f_{i-1,w(j-1),p-1}&p>0\\\max\limits_{wz=1}^n\max\limits_{k=0}^{min(i-1,p)}(f_{i-1,wz,k}-G_j)&p=0\end{cases} \]

\[w(x)=(x\bmod n+n)\bmod n==0?n:(x\bmod n+n)\bmod n \]

其中，\(r_{i,j}\)表示第\(i\)条路第\(j\)个时刻的金币，\(G_i\)表示在\(i\)个工厂买机器人的金币

初始化:\(\sum\limits_{i=1}^n f_{0,i,0}=G_i\)

我们发现可以降维，第三维其实可以用前缀和维护。

用\(f_{i,j}\)表示在第\(i\)个时刻走完后在工厂\(j\)买了机器的最大金币数

定义\(sum_{i,j}\)表示终点为\(i\)且走了\(j\)个时刻的金币

有\(sum_{i,j}=sum_{w(i-1),j-1}+r_{w(i-1),j}\)

定义函数\(val(st,la,ti)=sum_{w(st+ti),la+ti}-sum_{st,la}\)表示在第\(st\)个时刻第\(la\)个工厂开始走走了\(ti\)个时刻在道路上获得的金币，则有

\[f_{i.j}=-G_j+\max\limits_{st=1}^n\max\limits_{ti=1}^{min(i,p)}(f_{i-ti,st}+val(st,i-ti,ti)) \]

时间复杂度\(O(n^3)\)需要优化

考虑单调队列

该单调区间内记录\(gs,ks,pos\)，其中\(gs\)表示买上一个机器人时获得的最大金币数为\(gs\)（注意，记录的是买了后的最大金币数），\(ks\)表示上一个机器人在第\(ks\)个工厂买，\(pos\)表示在第\(pos\)个时刻买

求答案时取队首的\(q\)，则\(ans=q_{gs}+val(q_{ks},q_{pos},i-q_{pos})\)

然而单调队列要满足一个性质无论何时都要满足单调性，所以我们发现不可以把所有的数都放到同一个单调队列，因为不同道路上的金币不同的时刻可能不同，若我们把他们放到同一个单调队列，可能会导致在第一个时刻从工厂一开始会更优，第二个时刻的时候从工厂二开始会更优（只有从第三个工厂到第四个工厂的道路在第二个时刻的金币足够多，而其他的道路的金币又足够少）。相信~~丧心病狂~~的出题人会构造的。

那么我们可以构造多个单调队列，单调队列\(q_i\)维护所有假设这个机器人一直在走，那么第0个时刻在i的数，这样他们第\(k\)个时刻必定会走同一条道路。因为他在\(pos\)时刻开始走，所以当\(i-pos>p\)或者有更优解时把它踢出队列。

最后再在取每一个单调队列的队首计算答案取\(max\)即可

上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1010,INF=1e16;
ll n,m,p,tzy,ans=-INF;
ll r[N][N],G[N];
ll sum[N][N],f[N][N];
ll w(ll wz){return ((wz%n+n)%n)==0?n:((wz%n+n)%n);}
ll val(ll st,ll la,ll ti){return sum[w(st+ti)][la+ti]-sum[st][la];}
ll head[N],tail[N];
struct jgt{ll gs,ks,pos;}q[N][N];
void init()
{
	for(ll i=1;i<=m;i++)
	for(ll j=1;j<=n;j++)
	f[i][j]=-INF;
	for(ll i=1;i<=n;i++)
	f[0][i]=-G[i],head[i]=1;
}
int main()
{
	scanf("%lld %lld %lld",&n,&m,&p);
	for(ll i=1;i<=n;i++)
	for(ll j=1;j<=m;j++)
	scanf("%lld",&r[i][j]);
	for(ll i=1;i<=n;i++)
	scanf("%lld",&G[i]);
	for(ll i=1;i<=m;i++)
	for(ll j=1;j<=n;j++)
	sum[j][i]=sum[w(j-1)][i-1]+r[w(j-1)][i];
	init();
	for(ll i=1;i<=m;i++)
	{
		for(ll st=1;st<=n;st++)
		{
			while(head[w(st-i+1)]<=tail[w(st-i+1)]&&q[w(st-i+1)][tail[w(st-i+1)]].gs+val(q[w(st-i+1)][tail[w(st-i+1)]].ks,q[w(st-i+1)][tail[w(st-i+1)]].pos,i-q[w(st-i+1)][tail[w(st-i+1)]].pos)<f[i-1][st]+val(st,i-1,1)) tail[w(st-i+1)]--;
			q[w(st-i+1)][++tail[w(st-i+1)]]={f[i-1][st],st,i-1};
			while(i-q[w(st-i+1)][head[w(st-i+1)]].pos>p) head[w(st-i+1)]++;
		}
		tzy=-INF;
		for(ll j=1;j<=n;j++)
		tzy=max(tzy,q[j][head[j]].gs+val(q[j][head[j]].ks,q[j][head[j]].pos,i-q[j][head[j]].pos));
		for(ll j=1;j<=n;j++)
		f[i][j]=tzy-G[j];
	}
	for(ll i=1;i<=n;i++)
	ans=max(ans,f[m][i]+G[i]);
	printf("%lld\n",ans);
	return 0;
}