题目链接

题目大意

现在有一个 的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间 和一个参数 表示在时间 时会向 方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。
其中 ,区间个数 ，区间最大的右端点

题解

首先对于这个题目我们有一个很朴素的暴力，也就是记 表示在时间点 时自己在 能走到的最远距离，转移只需要考虑这个时间点是否让钢琴不动：
$x',y'O(Tn^2)kf_{i,x,y}i(x,y)dis(x,y)(x',y')(x',y')nO(n^3k)g = f_{i-1}xyxf_x \to f_{x+1}O(n^2k)$，可以通过该题。

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#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<val,pos>

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;
}