「NOI2005」瑰丽华尔兹

发布于 13 天前  37 次阅读


题目链接

题目大意

现在有一个 $n\times m$ 的矩阵,给定的起始点上有个钢琴,矩阵上有些方格是障碍物,用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动(上下左右),当然每个时间点可以选择让钢琴不动,不允许钢琴超出边界或者碰到障碍,询问钢琴可能走的最远距离是多少。
其中 $1 \leq n,m \leq 200$,区间个数 $k \leq 200$,区间最大的右端点 $ T \leq 40000$

题解

首先对于这个题目我们有一个很朴素的暴力,也就是记 $f_{i,x,y}$ 表示在时间点 $i$ 时自己在 $(x,y)$ 能走到的最远距离,转移只需要考虑这个时间点是否让钢琴不动:
$$f_{i,x,y} = min \{f_{i-1,x,y},f_{i-1,x',y'}+1\}$$
这里和下文中的 $x',y'$ 都默认是这个点能从哪里到来的位置。
显然这样的 dp 复杂度是 $O(Tn^2)$ 的,时间复杂度和空间复杂度都接受不了。
我们发现这个题目或许想让我们的复杂度与 $k$ 有关,于是我们可以考虑设 $f_{i,x,y}$ 表示在第 $i$ 个时间区间的时候,位置在 $(x,y)$ 能走的路径最大值。
不难发现这一段区间的决策可以拆成一段静止和一段不静止,所以我们可以得到转移方程:
$$f_{i,x,y} = min \{f_{i-1,x,y},f_{i-1,x',y'}+dis\}$$
这里 $dis$ 为点 $(x,y)$ 到点 $(x',y')$ 的曼哈顿距离,下文同理。
注意到这里可能的 $(x',y')$ 对最多有 $n$ 个,所以总复杂度为 $O(n^3k)$,需要考虑如何继续优化。
首先这个也可以滚动数组,于是我们设 $g = f_{i-1}$。式子可以重写成
$$f_{x,y} = min\{g_{x',y'}+dis\}$$
注意到每一段时间区间钢琴都是沿着水平线滑动的,也就是 $x$ 和 $y$ 至多改变一个。我们设这段区间转移时变化的维度是 $x$,忽略不变的那一维可以得到:
$$f_{x} = min\{g_{x+k}+|k|\}$$
这个式子在由 $f_x \to f_{x+1}$ 的过程中具有单调性,所以我们可以使用单调队列维护这一转移,时间复杂度变为 $O(n^2k)$,可以通过该题。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;
const int dx[4] = {-1,1,0,0};
const int dy[4] = {0,0,-1,1};

int n,m,sx,sy,k,now,ans;
char str[MAXN][MAXN];
int f[2][MAXN][MAXN];
P q[MAXN];// pair

inline void calc(int x,int y,int len,int d){
    d--;int head = 1,tail = 0;
    for(int i = 1;x >= 1 && x <= n && y >= 1 && y <= m;x += dx[d],y += dy[d],++i){
        if(str[x][y] == 'x') {head = 1,tail = 0;continue;}
        while(head <= tail && q[tail].fi + i - q[tail].se < f[now^1][x][y]) tail--;
        q[++tail] = MP(f[now^1][x][y],i);
        if(q[tail].se - q[head].se > len) head++;
        f[now][x][y] = q[head].fi + i - q[head].se;
        ans = std::max(ans,f[now][x][y]);
    }
}

int main(){
    scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&k);
    FOR(i,1,n) scanf("%s",str[i]+1);CLR(f,0xf3);
    f[now][sx][sy] = 0;
    while(k--){
        now ^= 1;int l,r,d;scanf("%d%d%d",&l,&r,&d);
        if(d == 1) FOR(i,1,m) calc(n,i,r-l+1,d);
        if(d == 2) FOR(i,1,m) calc(1,i,r-l+1,d);
        if(d == 3) FOR(i,1,n) calc(i,m,r-l+1,d);
        if(d == 4) FOR(i,1,n) calc(i,1,r-l+1,d);
    }
    printf("%d\n",ans);
    return 0;
}


一个OIer。