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

作者: wjyyy 分类: DP,解题报告 发布时间: 2019-06-19 17:25

点击量:183

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;
}

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Mayflyyh Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Mayflyyh
游客
Mayflyyh

大佬一周没更了

/* */