Magic Waltz

FriedrichC · 2022-08-10 15:58:50 · 题解

P2254 [NOI2005] 瑰丽华尔兹题解

题目传送门

题目背景

\text{-麻烦把琴刹关了。}

\footnotesize\text{-Take the brakes off,please.}

\text{-什么？你疯了？}

\footnotesize\text{-What? That's crazy!}

\text{-相信我，把琴刹关了。}

\footnotesize\text{-Trust me,Just take the brakes off.}

......

题目分析

首先设计状态，先考虑设 f(t,i,j) 表示 t 时刻，在第 i 行第 j 列的位置走过的最长路径长。状态转移方程为 f(t,i,j)=\max(f(t-1,i,j),f(t-1,i^\prime,j^\prime))。

其中 i^\prime 和 j^\prime为上一个合法的转移位置，即与当前位置同行或同列（取决于方向）的非家具位置。

显然这样做复杂度为 O(TNM)，必然超时。

考虑优化这个状态，设 f(k,i,j) 表示在第 k 时间段之中，在位置 (i,j) 的最长路径长。

表面上看，这个状态的复杂度并没有什么优化。

因为哪怕在第一维之中用时间段代替时刻，我们并不会因此而少维护状态，因为在每个时间段细分出的每个时刻仍然需要维护。

这样看来复杂度为 O(KN^2M)。与我们先前的做法别无二致。

但是，如果我们把状态转移方程写出来：

f(k,i,j)=\max\{f(k-1,i^\prime,j^\prime)+distance\}

下文将会说明，正因为这样设计状态，我们才得以优化。

这是很粗略的状态转移方程，因为我们还没有解决两个问题：上一个合法位置的确定和当前位置与其之间的距离（即 distance）。

那么，我们改如何优化这一转移呢？

转移优化

首先，上文已经提到了，上一个合法位置与当前的位置同行或同列，并具体取决于方向。

那么以当前时间段方向向南为例，设当前时间段长度为 len，我们有：

f(k,i,j)=\max\limits_{i-len\leqslant pos\leqslant i}\{f(k-1,pos,j)+i-pos\}

先要强调一点，(i,j) 位置的含义是第 i 行第 j 列，这意味着，如果我们要在类似样例图示的那种表格上建立一个坐标系，那么原点在左上角，y轴以向下为正方向。

所以仔细看方程中 pos 的范围，如果向南（也就是向下）移动，当前状态肯定是从上方状态转移过来，但是，由于正方向向下，上方点的 i 坐标是更小的值，而不是更大的值（这样就是以右下角为原点）。

我们之所以这样设计坐标是因为这样与数组的下标表示就吻合了，以便于我们使用数组和循环变量。

接下来对方程进行分析，

首先，从方程中我们可以看出，上文中的 distance 就只是区间中连续的位移增量，很好求解。

其次，由于方程之中当前位置确定，i 为定值，可以写成：

f(k,i,j)=\max\limits_{i-len\leqslant pos\leqslant i}\{f(k-1,pos,j)-pos\}+i

那么，关键的优化就在于求最大值的优化：

我们发现，方程中只有一个变量 pos，观察其取值范围，我们对于每个当前位置，可以由之转移的位置处在一段长度固定为 len 的连续区间之中。

这不就变成维护定长区间最值的问题，也就是滑动窗口的问题吗？

显然可以使用单调队列优化，那么原先维护区间最值的最坏 O(N) 复杂度均摊为 O(1)，整体复杂度优化至 O(KNM)，可以接受了。

至于空间复杂度，就可以用滚动数组优化。

附上代码

#include<bits/stdc++.h>
#define int long long
#define maxn 210
#define INF INT_MAX //用LLONG_MAX会导致减法溢出 
#define upd ans=max(ans,f[p][i][j])
#define chk if(a[i][j]=='x'){l=1;r=0;continue;}//遇到非法位置，直接清空队列
using namespace std;
int q[maxn],l=1,r;
char a[maxn][maxn];
int f[2][maxn][maxn];
int ans,p;
int n,m,x,y,k;
signed main()
{
    cin>>n>>m>>x>>y>>k;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)cin>>a[i][j];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            f[p][i][j]=-INF;
    f[p][x][y]=0;
    while(k--)
    {
        p^=1;//滚动数组
        int s,t,d;
        cin>>s>>t>>d;
        int len=t-s+1;
        if(d==1)
            for(int j=1;j<=m;++j)
            {
                l=1; r=0;//每次队列清空
                for(int i=n;i>=1;--i)
                {
                    chk;
                    while(l<=r&&f[p^1][q[r]][j]+q[r]<=f[p^1][i][j]+i)r--;
                    while(l<=r&&q[l]-i>len)l++;
                    q[++r]=i;
                    f[p][i][j]=f[p^1][q[l]][j]+q[l]-i;
                    upd;
                }
            }
        else if(d==2)
            for(int j=1;j<=m;++j)
            {
                l=1; r=0;
                for(int i=1;i<=n;++i)
                {
                    chk;
                    while(l<=r&&f[p^1][q[r]][j]-q[r]<=f[p^1][i][j]-i)r--;
                    while(l<=r&&i-q[l]>len)l++;
                    q[++r]=i;
                    f[p][i][j]=f[p^1][q[l]][j]+i-q[l];
                    upd;
                }
            }
        else if(d==3)
            for(int i=1;i<=n;++i)
                {
                    l=1; r=0;
                    for(int j=m;j>=1;--j)
                    {
                        chk;
                        while(l<=r&&f[p^1][i][q[r]]+q[r]<=f[p^1][i][j]+j)r--;
                        while(l<=r&&q[l]-j>len)l++;
                        q[++r]=j;
                        f[p][i][j]=f[p^1][i][q[l]]+q[l]-j;
                        upd;
                }
            }   
        else
            for(int i=1;i<=n;++i)
            {
                l=1; r=0;
                for(int j=1;j<=m;++j)
                {
                    chk;
                    while(l<=r&&f[p^1][i][q[r]]-q[r]<=f[p^1][i][j]-j)r--;
                    while(l<=r&&j-q[l]>len)l++;
                    q[++r]=j;
                    f[p][i][j]=f[p^1][i][q[l]]+j-q[l];
                    upd;
                }
            }
    }
    cout<<ans<<endl;
    return 0;
}

一些细节

在代码实现时，在各个方向上的处理都有些许不同，很容易犯错。

在内外层循环变量的确定上：

对于某一个方向，对于任意一个当前位置，pos 的取值与该方向的变化维度在同一维度上。

比如，如果是竖直方向，运动时变化的维度就是 i，所以 pos 与 i 在同一维度，那么 i 就在内层循环。
在枚举顺序的确定上：

以向北（向上）为例，内层循环枚举时是从 n 到 1 枚举，因为向上恰恰是y轴的负方向，所以在运动时 i 坐标会从大到小地变化。

所以枚举顺序要根据坐标轴方向来确定。
在弹栈条件的确定上：

是否弹栈，其实就取决于 distance 是否大于 len。

但是要注意 distance 的表达式，想清楚谁大谁小，还是以向北（向上）为例：

由于当前状态由下方状态更新而来，而下方点的 i 坐标更大，所以弹栈条件为q[l]-i>len。

~~这么看来全用绝对值函数也不是不行呢。~~

最后提一点，初始化所有状态为负无穷，起点除外。

因为本来只能从单点出发运动，由单点递推更新状态，如果其余状态不设置为负无穷，就相当于可以从多个点出发，显然不合逻辑。

结语

\text{陆地上的人们浪费了太多时间去问为什么。}

\footnotesize\text{I think you land people waste a lot of time wondering why.}

\text{冬天来临时，巴望着夏天，}

\footnotesize\text{Winter comes and you can't wait for summer.}

\text{夏天到来时，就已经开始害怕冬天。}

\footnotesize\text{Summer comes and you live in dread of winter.}

\text{所以人们永不厌倦旅行，}

\footnotesize\text{That's why you never tire of traveling.}

\text{总是在追寻，四季如春的远方。}

\footnotesize\text{Always chasing someplace far away where it's always summer.}

\text{——《海上钢琴师》}