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

Posted by xiaodao
Category: BZOJ