ABC146F Sugoroku

题意：

给定一个01串，从0出发，恰好到达n胜利，每次能走1~m步，且数字为1的位置不能走

问字典序最小的行走方法（即不仅走的次数要少，且越靠前走的步数越要少）

题解：

套路题，思路不算难想

step 1:

先设计dp考虑走的次数尽可能少的条件

设f[i]表示到i位置的最少步数

初始f[]=oo,f[0]=0

转移$f_i=\min \left \{ f_j|i-j<=m \right \}+1 (a_i==0)$

复杂度$O(nm)$

考虑优化dp

发现min部分就是个滑动窗口，于是上单调队列

复杂度降为$O(n)$

step2:

考虑题目的另一个要求：靠前的步数要尽可能少

因为总步数不变，靠前的要少，也就是说靠后的要多

也就是用g[]记录每次dp转移是从哪个位置转来的，如有相同则取前者转移

最后在dp后倒着从g[n]开始遍历，类似链表，每次g[n]与n的差就是这次走的步数

反着输出即可

代码实现也很简单，因为单调队列的先进后出的性质可以保证队首的下标是最小的，直接塞到g[]中即可

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int n,m,a[N],f[N],g[N];
deque<int> q;
vector<int> ans;

signed main(){
    read(n);read(m);
    for(int i=0;i<=n;i++) scanf("%1d",&a[i]),f[i]=0x3f3f3f3f;
    f[0]=0;
    f[n+1]=0x3f3f3f3f;
    q.push_back(0); //先塞个0进去
    for(int i=1;i<=n;i++) if(!a[i]){ //转移先决条件
        g[i]=n+1;
        while(!q.empty()&&q.front()+m<i) q.pop_front(); //维护单调队列
        if(!q.empty()) g[i]=q.front(); //维护g[]
        f[i]=f[g[i]]+1; //转移f[]
        while(!q.empty()&&f[q.back()]>f[i]) q.pop_back(); //维护单调队列
        q.push_back(i);
    }
    if(f[n]>n){
        write(-1); //走不到n则无解
        return 0;
    }
    for(;n;n=g[n]) ans.push_back(n-g[n]); //倒着类链表便利g[]
    for(int i=ans.size()-1;i>=0;i--) write(ans[i]),putchar(' '); //再倒着输出步数
}