首页 > 系统服务 > 详细

Loj #2687 - 「BalticOI 2013」Vim

时间:2020-01-15 00:41:19      阅读:43      评论:0      收藏:0      [点我收藏+]

标签:还要   优化   ()   space   dot   cout   

搞了一个 \(nk^2\) 的做法。

首先如果前面是一个 \(e\) 那下一步一定是将 \(e\) 删掉,花费 \(2\)

那么可以将 \(e\) 删掉,每个之前有 \(e\) 的点都必须经过,求最短的方案。

答案一定是向后走一段,然后把前面的所有必经点都走掉,于是可以轻松得到 \(O(n^2)\) 的做法。

现在考虑优化。

很容易想到的是每次只向后走一个,然后立即将前面所有必经点走掉。如果这个结论正确那状态是 \(nk\) 的,很容易转移。

然而需要注意这里向后走的费用是 \(2\),于是类似:
\[ \begin{aligned} &ca \dots aaba\&01 \dots 1011 \end{aligned} \]
这样的数据可以卡掉。

但是我们可以考虑一个更平凡的结论:

  • 考虑每次向后一段再向前,再向后一次,最终到达的那一个节点一定是第一次到达。

证明:例如:
\[ \begin{matrix} a & \to & \to & b &\to & c \ & d & \leftarrow &\leftarrow &\leftarrow&\leftarrow \ & & \to &\to &e \end{matrix} \]
我们显然可以改为:
\[ \begin{matrix} a & \to & \to & b & & c \ & d & \leftarrow & && \ & \to & \to &\to &e \ & & & b+1 & \leftarrow \ & & & \to& \to & c \end{matrix} \]
这样的话可以发现答案变小。

于是最终答案一定可以分为若干段,每一段从左边一直跳到右边,然后退回左边,并且两段之间无交。

于是我们考虑以下状态:
\(f(i,j)\) 表示当前在 \(i\),已经从 \(j\) 走到 \(i\) 的答案。

\(g(i,j)\) 表示当前在 \(j\),上一段的最右端是 \(i\) 的答案。

我们每次改变较小的还要改变的位置。

考虑转移有哪些:

第一种是 \(f(i,j) \to g(\text{next}(i),j)\) 即下一段第一个经过的是 \(j\)

第二种是 \(g(i,j) \to f(\text{first}(i+1,j),j)\) 即下一段退回到 \(i+1,j\) 这段的第一个必经点。

第三种是 \(g(i,j) \to f(\text{next}(i),j)\) 即上一段延长了。

不难发现 \(j\) 就是 \(i\) 或者 \(i\) 的后继节点,于是状态是 \(nk\) 的,转移 \(O(k)\) ,于是总复杂度 \(O(nk^2)\)

需要注意特判以下最后一段以及 \(i=j\) 的转移。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 7e4+5;
const int table[10]={0,1,2,3,-1,4,5,6,7,8};
int n;char s[N];
bool mark[N];
int ch[N],nxt[N][9],Last[N],f[N][9],g[N][9],Mark[N],h[N];
int ans=0x3f3f3f3f;

inline void Doit(int S){
    for(int y=0;y<9;y++)if(nxt[S][y]&&f[S][y]!=0x3f3f3f3f){
        if(Mark[nxt[S][y]+1]==0){
            ans=min(ans,f[S][y]);continue;
        }else{
            for(int j=0;j<9;j++)if(nxt[nxt[S][y]+1][j]){
                int ny = nxt[nxt[S][y]+1][j];
                ans=min(ans,f[S][y]+h[ny]+ny-nxt[S][y]);
            }
        }
        for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
            int to1=nxt[S][y], to2=nxt[S+1][y2];
            if(to2>=to1){
                int nxt = Mark[to1+1];nxt=min(nxt,to2);
                f[nxt][y2]=min(f[nxt][y2],to2-nxt+f[S][y]+2);
            }
            //if(to2<=to1) f[to2][y]=min(f[to2][y],2+f[S][y]);
        }
        int to1=nxt[S][y];
        if(to1==S){
            for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
                for(int y3=0;y3<9;y3++)if(nxt[S+1][y3]){
                    int to2=nxt[S+1][y2],to3=nxt[S+1][y3];
                    if(to2<to3)g[to2][y3]=min(g[to2][y3],f[S][y]+2+2+to2-S);
                }
            }
        }
        for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
            int to2=nxt[S+1][y2];
            if(to2>=to1)g[to1][y2]=min(g[to1][y2],f[S][y]+2);
        }
    }
    for(int y=0;y<9;y++)if(nxt[S][y]&&g[S][y]!=0x3f3f3f3f){
        for(int y2=0;y2<9;y2++)if(nxt[S+1][y2]){
            int to1=nxt[S][y], to2=nxt[S+1][y2];
            if(to2<=to1)g[to2][y]=min(2+to2-S+g[S][y],g[to2][y]);
        }
        int _nxt=min(Mark[S+1],nxt[S][y]);
        f[_nxt][y]=min(f[_nxt][y],g[S][y]+nxt[S][y]-_nxt);
    }
}

int main()
{
    cin >> n;
    scanf("%s",s+1);
    int _n=0;
    int ans2=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='e'){ans2+=2;continue;}
        else ch[++_n]=table[s[i]-'a'],mark[_n]=s[i-1]=='e';
    }
    mark[1]=1;n=_n;
    for(int i=n;i;i--){
        Mark[i]=mark[i]?i:Mark[i+1];
        Last[ch[i]]=i;
        for(int j=0;j<9;j++)nxt[i][j]=Last[j];
    }
    for(int i=n;i;i--){
        h[i]=0x3f3f3f3f;if(!Mark[i+1])h[i]=2;
        for(int j=0;j<9;j++)if(nxt[i+1][j]){
            int nx=nxt[i+1][j];
            if(nx)h[i]=min(h[i],h[nx]+2+nx-i);
        }
    }
    for(int i=1;i<=n;i++)for(int j=0;j<9;j++){g[i][j] = f[i][j] = 0x3f3f3f3f;}
    f[1][ch[1]]=0;
    for(int i=1;i<=n;i++)Doit(i);
    cout << ans + ans2 << endl;
}

Loj #2687 - 「BalticOI 2013」Vim

标签:还要   优化   ()   space   dot   cout   

原文:https://www.cnblogs.com/weiyanpeng/p/12194639.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号