专栏文章

题解：P14508 猜数游戏 guess

SSktic
P14508题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5gzls
此快照首次捕获于
2025/12/01 20:53
3 个月前
此快照最后确认于
2025/12/01 20:53
3 个月前
查看原文
看到题，第一反应是建模图论。记 A=max⁡i=1maiA=\max_{i=1}^ma_i，显然有效的移动只会在[−A,n+A][-A,n+A] 内进行，于是考虑把区间内部的每个位置等效到一个点，对于每个点连 2m2m 条边对应走法，求走遍 1∼n1\sim n 每个点的最短距离，即能够保证对于每个点而言都存在某次移动的询问边界取到它本身，即每个点存在一个不同于其他点的询问返回值。
但是这个东西看起来是非常不可做的，于是我们需要另辟蹊径。
考虑到这个棋盘是无穷大且重复的，我们要求 [i,j][i,j] 下的答案，它与平移到第一位求 [1,j−i+1][1,j-i+1] 没有本质不同，注意到这是一个非常完美的最优子结构性质，于是考虑进行动态规划。
我们定义 dpidp_i 表示解决 [1,i][1,i] 区间内的问题需要的最小代价。[1,i][1,i] 根据第一次移动可以被划分为 [1,j][1,j]，[j+1,i][j+1,i] 进行求解。
我们先从 11 移动到 jj，最少花费 disjdis_j 的代价。这个时候进行分类讨论，如果答案不在 [1,j][1,j]，我们就在 [j+1,i][j+1,i] 中寻找答案，这部分可以通过平移化为 [1,i−j][1,i-j]。如果答案在 [1,j][1,j] 中，那么我们就再在 [1,j][1,j] 中求解。因此要取 dpjdp_j 与 dpi−jdp_{i-j} 中较大的一个。
于是得到转移方程：
dpi=minj=1i−1{max{dpi,dpi−j}+disj}dp_i=\mathop{\text{min}}\limits_{j=1}^{i-1}\{\text{max}\{dp_i,dp_{i-j}\}+dis_{j}\}
计算 disjdis_j 的过程可以使用堆优化的最短路进行求解（注意不能使用先加后减的多重背包），时间复杂度 Θ(mAlog⁡mA)\Theta(mA\log mA)，动态规划的时间复杂度 Θ(n2)\Theta(n^2)，会超时，考虑优化。
发现其实转移时，如果 jj 超过了 AA，本质上是从 dpjdp_j 跳了好几步走到 dpidp_i，这部分直接舍去即可。于是动态规划时间复杂度优化到了 Θ(nA)\Theta(nA)，多测情况下可以通过该题。
注意几个实现时的细节：
  1. 代价极限数据下会超过 int 的数据范围，需要开 ll。
  2. 最短路由于在进行松弛操作时可能会出现下标为负的点，因此考虑将所有点右移 AA 位后再进行求解，动态规划时候还原。
  3. 如果暴力建图再进行最短路会导致总边数上界达到 6nmT6nmT 导致 MLE\text{MLE}，因此需要在最短路松弛操作内部直接根据 mm 进行遍历。
AC Code:
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+10;
const int maxm=5e3+10;
typedef long long ll;
const ll INF=1e18;
int n,m,mxk,mnk;
ll dp[maxn],dis[maxm<<2];
struct move
{
	int k;
	ll v;
}mov[maxm];
struct edge
{
	int v;
	ll w;	
};
struct node
{
	int k;
	ll dis;
	bool operator <(const node &uu)const
	{
		return dis>uu.dis;
	}	
};
priority_queue<node>q;
int vis[maxm<<2];
void dijkstra()
{
	for(int i=0;i<=2*n+1;i++)
		dis[i]=INF,vis[i]=0;
	dis[mxk]=0;
	q.push({mxk,0}); 
	while(!q.empty())
	{
		int k=q.top().k;
		q.pop();
		if(vis[k])
			continue;
		vis[k]=1;
		for(int i=1;i<=m;i++)
		{
			if(k-mov[i].k<0)
				continue;
			int to=k-mov[i].k;
			ll w=mov[i].v;
			if(dis[k]+w<dis[to])
			{
				dis[to]=dis[k]+w;
				q.push({to,dis[to]});
			}
		}
		for(int i=1;i<=m;i++)
		{
			if(k+mov[i].k>2*n+1)
				continue;
			int to=k+mov[i].k;
			ll w=mov[i].v;
			if(dis[k]+w<dis[to])
			{
				dis[to]=dis[k]+w;
				q.push({to,dis[to]});
			}
		}
	}
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	int c,t;
	cin>>c>>t;
	while(t--)
	{
		mxk=0,mnk=INF;
		cin>>n>>m;
		for(int i=1;i<=m;i++)
		{
			cin>>mov[i].k;
			mxk=max(mxk,mov[i].k);
			mnk=min(mnk,mov[i].k);
		}
		for(int i=1;i<=m;i++)
			cin>>mov[i].v;
		dijkstra();
		fill(dp,dp+1+n,INF);
		dp[1]=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=min(i-1,mxk);j++)
				dp[i]=min(dp[i],max(dp[j],dp[i-j])+dis[j+mxk]);
//		for(int j=0;j<=min(n,mxk);j++)
//			cout<<j<<"v "<<dis[j+mxk]<<endl;
		if(dp[n]==INF)
			cout<<-1<<endl;
		else
			cout<<dp[n]<<endl;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...