http://www.lydsy.com/JudgeOnline/problem.php?id=1499

### Brief description:

略。）

### Analysis:

單調隊列 DP。）

//}/* .................................................................................................................................. */ const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int N = int(2e2) + 9; char Map[N][N]; int dp[2][N][N], p, q, s, t, d; int n, m; void gao(int x, int y, int w){ static PII Q[N]; int cz = 0, op = -1; REP(i, w){ if (Map[x][y] == 'x'){ cz = 0, op = -1; } else{ while(cz <= op && i - Q[cz].fi > t) ++cz; while(cz <= op && dp[q][x][y] - i > Q[op].se) --op; Q[++op] = MP(i, dp[q][x][y] - i); dp[p][x][y] = Q[cz].se + i; } x += dx[d], y += dy[d]; } } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int K, x, y; RD(n, m, x, y, K); REP_1(i, n) RS(Map[i]+1); p = 0, q = 1; FLC(dp[p], 0x80); dp[p][x][y] = 0; DO(K){ swap(p, q); FLC(dp[p], -1); RD(s, t, d); t -= s; ++t; --d; if (d == 0){ REP_1(i, m) gao(n, i, n); } else if (d == 1){ REP_1(i, m) gao(1, i, n); } else if (d == 2){ REP_1(i, n) gao(i, m, m); } else if (d == 3){ REP_1(i, n) gao(i, 1, m); } } int z = 0; REP_2_1(i, j, n, m) checkMax(z, dp[p][i][j]); OT(z); }

### References:

http://www.cnblogs.com/kedebug/archive/2013/02/28/2937861.html