【LOJ#2687】Vim（动态规划）

短命女 2021-11-16 09:36 104阅读 0赞

# 【LOJ\#2687】Vim（动态规划） #

## 题面 ##

[LOJ][]

## 题解 ##

发现移动的路径一定是每次往后跳到下一个某个字符的位置，然后往回走若干步，删掉路径上的所有\\(e\\)，然后继续执行这个操作。  
这里稍微介绍一下线头\\(dp\\)，大概是把转移的路径画出来，最终要求能形成一个环，而每一个需要\\(dp\\)的位置代表一个点，我们要从一个点转移过来，再从这个点转移出去，一进一出形成了一段弧线，我们要维护的就是这个弧线的形态。更加详细的可以参考[这里][Link 1]。  
因为我们的操作如此，所以我们把每次移动所跨越的区间做一个覆盖，不难发现要么被覆盖\\(1\\)次，要么被覆盖\\(3\\)次，以及一段后缀可能覆盖\\(0\\)次。  
我们提前把\\(e\\)给删掉，这样子剩下的位置只有两种，一种是关键点，即某个\\(e\\)连续段后的第一个非\\(e\\)字符所在的位置。另外一种不是关键点，并且关键点之间不可能相邻  
我们考虑记录这个状态，设\\(f\[i\]\[j\]\\)表示当前在\\(i\\)位置，并且\\(i,i+1\\)之间的这条线段被覆盖的次数为\\(1\\)次的接下来要跳到\\(j\\)字母的最小代价。设\\(g\[i\]\[j\]\[k\]\\)表示当前在\\(i\\)位置，\\(i,i+1\\)要覆盖三次，因为被覆盖三次所以会有两次向后跳的操作，第一次跳到了\\(j\\)字符，第二次跳到了\\(k\\)字符的最小代价。注意到这个状态中，并不代表着是从\\(i\\)位置往后跳\\(j\\)，而是从\\(i\\)位置之前的某个位置到达\\(i\\)之后\\(j\\)字符的最小代价。  
首先考虑\\(f\[i\]\[j\]\\)的转移：

*  如果\\(i\\)位置不是\\(e\\)，并且\\(s\[i\]\\neq j\\)那么可以从\\(f\[i-1\]\[j\]\\)转移过来，显然不需要额外代价。
 *  然后可以从\\(f\[i-1\]\[s\[i\]\]\\)转移到\\(f\[i\]\[j\]\\)，然后这里要进行一次\\(f\\)操作，而\\(f\\)后面还需要再跟上一个字符，所以代价为\\(2\\)。

接下来把\\(g\[i\]\[j\]\[k\]\\)也丢进来转移。

*  首先\\(g\[i\]\[s\[i\]\]\[k\]\\)等价于\\(f\[i\]\[k\]\\)，所以\\(f\[i\]\[j\]\\)可以从\\(g\[i\]\[s\[i\]\]\[k\]\\)转移过来，不需要代价。
 *  接下来\\(g\[i\]\[s\[i\]\]\[s\[i\]\]\\)跳完之后还是在自己这个位置，所以\\(f\[i\]\[j\]\\)可以由\\(g\[i\]\[s\[i\]\]\[s\[i\]\]\\)转移过来，代价为\\(2\\)。

然后考虑\\(g\\)怎么转移，先考虑\\(g\\)从\\(f\\)的转移

*  首先\\(g\[i\]\[j\]\[k\]\\)可以认为我们先走到\\(j\\)然后往回走一步使得\\((i,i+1)\\)被覆盖次数变成\\(3\\)，然后再跳到\\(k\\)，所以步数是\\(f\[i-1\]\[k\]+1+2\\)
 *  然后可以是先跳到\\(i\\)位置，再跳到\\(j\\)位置，再往回走，再跳到\\(k\\)位置，所以是\\(g\[i\]\[j\]\[k\]\\)可以由\\(f\[i-1\]\[s\[i\]\]+2+1+2\\)
 *  然后是我们可以从\\(g\[i-1\]\[j\]\[k\]\\)转移到\\(g\[i\]\[j\]\[k\]\\)，代价是\\(1\\)。因为要补上\\((i,i+1)\\)要被覆盖三次的代价。
 *  然后可以从\\(g\[i-1\]\[j\]\[s\[i\]\]\\)转移到\\(g\[i\]\[j\]\[k\]\\)代价是\\(3\\)。
 *  然后\\(g\[i-1\]\[s\[i\]\]\[k\]\\)转移到\\(g\[i\]\[j\]\[k\]\\)，代价是\\(3\\)。
 *  \\(g\[i-1\]\[s\[i\]\]\[s\[i\]\]\\)转移到\\(g\[i\]\[j\]\[k\]\\)，代价是\\(5\\)。

最后几个为啥是对的就和上面类似的分析就好了。  
可以参考[Itst博客的图][Itst]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define MAX 77777
    int n,cnt,a[MAX],f[MAX][11],g[MAX][11][11];
    char s[MAX];bool book[MAX];
    void cmin(int &x,int y){x=x>y?y:x;}
    int main()
    {
        scanf("%d%s",&n,s+1);
        for(int i=1;i<=n;++i)a[i]=s[i]-97;
        for(int i=2;i<=n;++i)
            if(a[i]==4)++cnt;
            else if(a[i-1]==4)book[i]=true;
        memset(f,63,sizeof(f));memset(g,63,sizeof(g));
        f[0][a[1]]=0;
        for(int i=1;i<=n;++i)
        {
            if(a[i]==4)
            {
                for(int j=0;j<11;++j)f[i][j]=f[i-1][j];
                for(int j=0;j<11;++j)
                    for(int k=0;k<11;++k)
                        g[i][j][k]=g[i-1][j][k];
                continue;
            }
            for(int j=0;j<11;++j)
            {
                if(j!=a[i]&&!book[i])cmin(f[i][j],f[i-1][j]);
                cmin(f[i][j],f[i-1][a[i]]+2);
                if(j!=a[i])cmin(f[i][j],g[i-1][a[i]][j]);
                cmin(f[i][j],g[i-1][a[i]][a[i]]+2);
                for(int k=0;k<11;++k)
                {
                    if(j!=a[i])cmin(g[i][j][k],f[i-1][j]+3);
                    cmin(g[i][j][k],f[i-1][a[i]]+5);
                    if(j!=a[i]&&k!=a[i])cmin(g[i][j][k],g[i-1][j][k]+1);
                    if(j!=a[i])cmin(g[i][j][k],g[i-1][j][a[i]]+3);
                    if(k!=a[i])cmin(g[i][j][k],g[i-1][a[i]][k]+3);
                    cmin(g[i][j][k],g[i-1][a[i]][a[i]]+5);
                }
            }
        }
        printf("%d\n",f[n][10]+cnt*2-2);
        return 0;
    }

转载于:https://www.cnblogs.com/cjyyb/p/11146822.html

[LOJ]: https://loj.ac/problem/2687
[Link 1]: https://blog.csdn.net/frankchenfu/article/details/94480631
[Itst]: https://www.cnblogs.com/Itst/p/10339605.html