GuOJ 1198「HB 省队互测 2019 Round1 Day1」轮回 题解【DP】

点击量：518

dp 能力又一次严重下降。

目录

题目背景

孤独者的唯一救赎就是绝对而永恒的孤独。

北斗是一个喜欢玩游戏的女孩子。

今天她蒯来一部叫《CROSS † CHANNEL》的游戏准备玩，但是没玩几下就发现，这个游戏的章节并不是按照剧情发展顺序来排的！这太糟糕了！北斗准备把这个游戏的所有章节重新排序，然后再开始玩。现在北斗想要知道她最快还要多久才能玩到游戏，你能帮帮她吗？

题目描述

这款游戏共有 $n$ 个章节，按照剧情顺序以 $1\sim n$ 标号。初始时这些章节是乱序的。

北斗可以执行如下两种操作。

1. 选择一个章节并向前挪到任意位置。这一步需要消耗时间 $b$。

2. 选择一个章节并向后挪到任意位置。这一步需要消耗时间 $a$。

北斗的目标是把这些章节按照升序排好。

输入格式

第一行三个正整数 $n,a,b$。

接下来一行是一个 $1\sim n$ 的排列，表示初始时章节的顺序。

输出格式

输出一行一个数，表示把所有章节按顺序排好所花费的最少时间。

样例

样例 1 输入

2 50 100 
2 1

样例 1 输出

50

样例 2 输入

3 10 100 
2 3 1

样例 2 输出

20

样例 3 输入

10 1 1 
5 2 3 6 8 7 9 4 1 10

样例 3 输出

4

样例 4 输入

10 3 2 
10 9 8 7 6 5 4 3 2 1 

样例 4 输出

18

样例 5 输入

10 2 3 
10 9 7 6 8 4 5 2 3 1

样例 5 输出

17

数据范围与约定

测试点编号	$n$	特殊性质
$1$	$\le 2$	无
$2$	$\le 6$	无
$3\sim 6$	$\le 100$	无
$7\sim 10$	$\le 5000$	$a=b$
$11\sim 12$	$\le 5000$	初始时章节倒序排列
$13\sim 20$	$\le 5000$	无

对于所有数据，满足 $n\ge 1,1\le a,b\le 10^9$。

题解

这个题的 $35$ 分还是比较好拿的。分别是 $1,7\sim12$ 号点。

对于 $1$ 号点，如果排列是 $\{1,2\}$，则输出 $0$，否则输出 $\min\{a,b\}$。

对于 $7\sim 10$ 号点，有 $a=b$。所以朝前朝后移都是一样的。那么贪心地认为除了 LIS 上的点都需要修改，那么输出 $a\times |LIS|$ 就可以了。

对于 $11,12$ 号点，把整个序列全部倒转过来，至少需要 $n-1$ 次操作，那么输出 $\min\{a,b\}\times(n-1)$ 即可。

那么对于整道题来说，是个比较有意思的 dp。

dp 的核心在于，状态的阶段是权值从小到大而不是位置从左往右。这个如果可以推广到一些棘手的问题中，可能可以获得一些新思路。

同样，第二维的设立也很重要。由于我们对于一个元素的移动是可以到一定方向的任意位置的，而在 dp 的中间阶段，这个位置是没有确定的。而 dp 的一个状态，要用确定且有效的一个量来保存。

所以我们选择“最大的没有被移动的数”作为第二维，它是确定的，并称之为 $j$。对于有效而言，它比其他较小的没有被移动的数更有效。因为一旦最大的数确定了，那么比它小的没有移动的数肯定在它前面，所以存最大的数能代表的信息最多。

然后分析没有确定的数，对于那些比 $j$ 小的，它一定在 $j$ 所在的位置 $p_j$ 之前，在之前的状态已经排好了，这时就不用管了。对于那些比 $j$ 大的，需要排在 $j$ 后面，而具体的位置还没有确定，也就是可以在 $j$ 后面任意有序放置。既然它是由 $j$ 决定的一个序列，那么就先把它放在 $j$ 的后面，认为它们的位置是 $(p_j,p_{j+1})$ 范围内的一个实数。

因此 $f_{i,j}$ 表示将序列中的元素 $[1,i]$ 按升序排列，且最大的没有被移动的数是 $j$ 的最小时间 $(j\in[0,i])$。

接下来我们就可以 dp 了，每次需要枚举上一阶段最大没有被移动的数 $j$，然后判断 $p_j$ 与 $p_i$ 的大小关系。

如果 $p_j>p_i$，那么要排成有序，在 $1\sim i-1$ 都确定的情况下，必须把 $i$ 向后移动。

如果 $p_j<p_i$，那么要排成有序，而且对位置在 $(p_j,p_i)$ 之间的数没有影响，必须把 $i$ 向前移动；由于上面认为权值在 $(j,i)$ 中的数位置在 $(p_i,p_{i+1})$ 区间内有序，因此

那么有状态转移方程
$$
f_{i,j}=\left\{
\begin{aligned}
&f_{i-1,j}+a&,p_j>p_i\\
&f_{i-1,j}+b&,p_j<p_i
\end{aligned}
\right.,0\le j<i\\
f_{i,i}=\min_{1\le j<i,p_j<p_i}\{f_{i-1,j}\}
$$

这样就可以在 $O(n^2)$ 的时间内完成这题了。

Code：

#include<cstring>
#include<cstdio>
#ifdef wjyyy
    #define gc getchar
#else
    #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[2100000],*p1=buf,*p2=buf;
int read()
{
    int x=0;
    char ch=gc();
    while(ch<'0'||ch>'9')
        ch=gc();
    while(ch>='0'&&ch<='9')
    {
        x=x*10+(ch&15);
        ch=gc();
    }
    return x;
}
int a[5050];
long long f[5050][5050];
int main()
{
    memset(f,0x3f,sizeof(f));
    int n,A,B;
    n=read();
    A=read();
    B=read();
    for(int i=1;i<=n;++i)
        a[read()]=i;
    f[0][0]=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<i;++j)
            if(a[j]>a[i])
                f[i][j]=f[i-1][j]+A;
            else
            {
                f[i][j]=f[i-1][j]+B;
                f[i][i]=f[i][i]<f[i-1][j]?f[i][i]:f[i-1][j];
            }
    }
    long long ans=0x7fffffffffffffff;
    for(int i=0;i<=n;++i)
        ans=ans<f[n][i]?ans:f[n][i];
    printf("%lld\n",ans);
    return 0;
}