题面
Sol
暴力：(设f[i][j][k])表示到第(i)次倾斜，当前在((j, k))的滑动最大距离
然后(O(n*m*T))转移，(AC)了？？？
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(205);
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, m, k, x, y, mp[_][_], T;
int s[_], t[_], d[_], dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1};
int f[2][_][_], ans;
int main(RG int argc, RG char* argv[]){
n = Input(), m = Input(), x = Input(), y = Input(), k = Input();
for(RG int i = 1; i <= n; ++i)
for(RG int j = 1; j <= m; ++j){
RG char op; scanf(" %c", &op);
mp[i][j] = (op == 'x');
}
for(RG int i = 1; i <= k; ++i)
s[i] = Input(), t[i] = Input(), d[i] = Input() - 1;
Fill(f, -127), f[0][x][y] = 0;
for(RG int T = 1; T <= k; ++T){
RG int nxt = T & 1, lst = nxt ^ 1;
for(RG int i = 1; i <= n; ++i)
for(RG int j = 1; j <= m; ++j)
f[nxt][i][j] = f[lst][i][j];
for(RG int i = 1; i <= n; ++i)
for(RG int j = 1; j <= m; ++j)
for(RG int p = 0; p <= t[T] - s[T] + 1; ++p){
RG int xx = i + p * dx[d[T]], yy = j + p * dy[d[T]];
if(xx < 1 || yy < 1 || xx > n || yy > m || mp[xx][yy]) break;
f[nxt][xx][yy] = max(f[nxt][xx][yy], f[lst][i][j] + p);
}
}
for(RG int i = 1; i <= n; ++i)
for(RG int j = 1; j <= m; ++j)
ans = max(ans, f[k & 1][i][j]);
printf("%d
", ans);
return 0;
}
然后每次要么是一行一行转移，要么一列一列转移
分开写发现是可以单调队列优化的
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(205);
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, m, k, x, y, mp[_][_];
int s[_], t[_], d[_], dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1};
int f[_][_], ans;
struct Queue{
int val, p;
} Q[_];
IL void Solve(RG int X, RG int Y, RG int T, RG int D){
RG int l = 0, r = -1;
for(RG int i = 0; ; ++i){
if(mp[X][Y]) l = 0, r = -1;
else{
while(l <= r && f[X][Y] - i > Q[r].val) --r;
Q[++r] = (Queue){f[X][Y] - i, i};
while(l <= r && i - Q[l].p > T) ++l;
f[X][Y] = Q[l].val + i;
}
X += dx[D], Y += dy[D];
if(X < 1 || Y < 1 || X > n || Y > m) break;
}
}
int main(RG int argc, RG char* argv[]){
n = Input(), m = Input(), x = Input(), y = Input(), k = Input();
for(RG int i = 1; i <= n; ++i)
for(RG int j = 1; j <= m; ++j){
RG char op; scanf(" %c", &op);
mp[i][j] = (op == 'x');
}
for(RG int i = 1; i <= k; ++i)
s[i] = Input(), t[i] = Input(), d[i] = Input() - 1;
Fill(f, -127), f[x][y] = 0;
for(RG int T = 1; T <= k; ++T){
RG int len = t[T] - s[T] + 1;
if(d[T] == 0)
for(RG int i = 1; i <= m; ++i) Solve(n, i, len, 0);
else if(d[T] == 1)
for(RG int i = 1; i <= m; ++i) Solve(1, i, len, 1);
else if(d[T] == 2)
for(RG int i = 1; i <= n; ++i) Solve(i, m, len, 2);
else
for(RG int i = 1; i <= n; ++i) Solve(i, 1, len, 3);
}
for(RG int i = 1; i <= n; ++i)
for(RG int j = 1; j <= m; ++j)
ans = max(ans, f[i][j]);
printf("%d
", ans);
return 0;
}