题解：B3734 [信息与未来 2017] 加强版密码锁

guoshengyu1231 · 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));
}

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

状态

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

其次，要想知道是否单调递增，那具体的数是必须得知道的，所以我们可以总结出状态。