# 某島

… : "…アッカリ～ン . .. . " .. .
October 1, 2014

## BZOJ 1499. [NOI2005]瑰麗華爾茲

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

### Analysis:

```//}/* .................................................................................................................................. */

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