自动搬运

查看原文

来自洛谷，原作者为

	guoshengyu1231 **

搬运于2025-08-24 21:14:42，当前版本为作者最后更新于2025-05-05 11:32:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意简述

有一个 $n$ 个拨盘的密码锁，每个拨盘的初始数字由给定的伪随机数列 $R$ 生成（第 $i$ 个拨盘的初始数字为 $R_i \bmod 100$）。每个拨盘的数字可以在 $0$ 到 $99$ 之间调整，调整规则如下：

• 向上拨‌：数字 $x$ 变为 $(x + 1) \bmod 100$（每次加 $1$，循环递增）。
• ‌向下拨‌：数字 $x$ 变为 $(x + 99) \bmod 100$（每次减 $1$，循环递减）。

每次拨动一个拨盘 $k$ 次（无论是向上还是向下），需要花费 $k^2$ 单位时间。目标是让所有拨盘的数字从左到右形成一个‌严格递增的数列‌（即前一个数字严格小于后一个数字），求达成这一目标所需的最少时间。

输入：

• 两个整数 $n$（拨盘数量）和 $R_1$（随机数列的首项）。
• 随机数列 $R$ 的生成规则：$R_i = (R_{i-1} × 6807 + 2831)\bmod 201701，i>1$。
• 第 $i$ 个拨盘的初始数字为 $R_i \bmod 100$。

输出：

• 解开密码锁的最少时间（即拨动次数的平方和的最小值）。

关键点：

• ‌严格递增‌：必须满足 $a_1 < a_2 <\dots< a_n$。
• ‌拨动代价‌：拨动 $k$ 次的花费是 $k^2$，与方向无关。
• ‌数字范围‌：数字是模 $100$ 循环的（如 $99+1=0$，$0-1=99$）。
• ‌随机数列‌：拨盘的初始数字由伪随机数列生成，需先计算出每个 $R_i \bmod 100$。

思路

既然是要我们算出解开密码锁的最少时间，那大概可以知道应该是动态规划了，那具体怎么做呢？先别急，首先这是一道绿题，说明还是有点难度的。所以遇到这种大问题，我们应该将他分解成若干个小问题，再逐个击破。俗话说，大事化小，小事化了，尽量把复杂的问题分解成简单的问题，做题也是一样。既然这题比较难，那我们就逐个击破。 $\\$

首先，我们既然是要通过拨动拨盘来让消耗的时间越少，那当务之急必然是算出拨动拨盘的代价。具体的，设 $cost_{i,j}$ 表示从数字 $i$ 拨到数字 $j$ 所需的代价。不难发现，从数字 $i$ 拨到数字 $j$，无非就是往上拨更优还是往下拨更优。根据题意模拟即可：

const int maxn=100;
int mul(int x){return x*x;}
void init()
{
	for(int i=0;i<maxn;i++)
	 for(int j=0;j<maxn;j++)
	  if(j>i) cost[i][j]=min(mul(j-i),mul(100+i-j));
	  	 else cost[i][j]=min(mul(i-j),mul(100+j-i));
}

其次，既然是动态规划，那三要素可不能少。

状态

要想知道状态，我们得先知道那些因素是与答案有关系的。首先枚举到第几个拨盘一定是有关系的。因为想要知道是不是满足严格递增，你总得知道前一个是啥呀。 $\\$

其次，要想知道是否单调递增，那具体的数是必须得知道的，所以我们可以总结出状态。 $dp_{i,j}$ 表示使前 $i$ 个拨盘单调递增，并且第 $i$ 个拨盘拨到 $j$ 时需要的最少时间。

边界

首先肯定要把 $dp$ 数组赋值为无穷大。接下来考虑只有一个拨盘的情况。很明显，当只有一个拨盘的时候，我们直接拨动这个拨盘即可。很容易写出代码：

for(int i=0;i<maxn;i++)
 dp[1][i]=cost[a[1]][i];

转移

接下来便是动态规划中最难的一步——状态转移。考虑到所有数据满足 $1\le N\le 100$。所以即便时 $O(n^3)$ 的 dp 也依然能过。那接下来我们可以考虑枚举一个中间变量来实现状态转移，那到底怎么转呢？考虑到第 $i$ 个拨盘的状态依赖第 $i-1$ 个拨盘的状态，那这个中间变量肯定是跟第 $i-1$ 哥拨盘相关，那可以是什么呢？显然应该是第 $i-1$ 个拨盘拨的数，不妨设该变量为 $k$，接下来就该考虑怎么写状态转移方程了。

状态转移方程

首先枚举 $k\in[0,j-1]$，因为 $k$ 是第 $i-1$ 个拨盘拨的数，要想使数列单调递增，那 $k$ 必然小于 $j$，那接下来状态转移方程就很好想了。我们可以理解为先把前一个拨盘拨到 $k$，再将这一个拨盘拨到 $j$，可得状态转移方程：

$$dp_{i,j}=\min^{k=0}_{k<j}\{dp_{i-1,k}+cost_{a_i,j}\} $$

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100;
int cost[maxn+5][maxn+5];
int a[maxn+5],n,x;
int dp[maxn+5][maxn+5];
int mul(int x){return x*x;}
void init()
{
	for(int i=0;i<maxn;i++)
	 for(int j=0;j<maxn;j++)
	  if(j>i) cost[i][j]=min(mul(j-i),mul(100+i-j));
	  	 else cost[i][j]=min(mul(i-j),mul(100+j-i));
}
//初始化cost数组
signed main()
{
	init();
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	 {
	 	a[i]=x%100;
	 	x=(x*6807+2831)%201701;
	 }
	memset(dp,0x3f,sizeof dp);
	for(int i=0;i<maxn;i++)
	 dp[1][i]=cost[a[1]][i];//初始化边界
	for(int i=2;i<=n;i++)
	 for(int j=0;j<maxn;j++)
	  for(int k=0;k<j;k++)
	   dp[i][j]=min(dp[i][j],dp[i-1][k]+cost[a[i]][j]);//状态转移
	int ans=1e18;
	for(int i=0;i<maxn;i++) ans=min(ans,dp[n][i]);//计算答案，应该不用我多说了吧
	cout<<ans;
	return 0;
}