题目地址：BZOJ：Problem 3208. — 花神的秒题计划Ⅰ

题目描述

背景【backboard】：
Memphis等一群蒟蒻出题中，花神凑过来秒题……
描述【discribe】：
花花山峰峦起伏，峰顶常年被雪，Memphis打算帮花花山风景区的人员开发一个滑雪项目。
我们可以把风景区看作一个n*n的地图，每个点有它的初始高度，滑雪只能从高处往低处滑【严格大于】。但是由于地势经常变动【比如雪崩、滑坡】，高度经常变化；同时，政府政策规定对于每个区域都要间歇地进行保护，防止环境破坏。现在，滑雪项目的要求是给出每个n*n个点的初始高度，并给出m个命令，C a b c表示坐标为a,b的点的高度改为c；S a b c d表示左上角为a,b右下角为c,d的矩形地区开始进行保护，即不能继续滑雪；B a b c d表示左上角为a b,右下角为c d的矩形地区取消保护，即可以开始滑雪；Q表示询问现在该风景区可以滑雪的最长路径为多少。对于每个Q要作一次回答。
花神一看，这不是超简单！立刻秒出了标算~

题意简述

动态改变点权和点的可用性的滑雪DP。

输入输出格式

输入格式：
第一行n，第二行开始n*n的地图，意义如上；接下来一个m，然后是m个命令，如上

输出格式：
对于每一个Q输出单独一行的回答

输入输出样例

输入样例#1：

5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
5
C 1 1 3
Q
S 1 3 5 5
S 3 1 5 5
Q

输出样例#1：

24
3

说明

样例解释：
第一个Q路线为：25->24->23->22….->3->2
第二个Q的路线为：10->9->2
100%的数据：1<=n<=700;1<=m<=1000000;其中Q、S、B操作总和<=100;
题中所有数据不超过2*10^9

题解

动态滑雪。
考虑到QSB操作操作很少，我们是可以接受O(n^3)的复杂度的，因此暴力改，每次全图重新跑记忆化搜索即可。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline bool isop(char c) {
    return c == 'C' || c == 'S' || c == 'B' || c == 'Q';
}

inline char readop() {
    char c;
    while(!isop(c = fgc())) {}
    return c;
}

const int MAXN = 705;
const int fix[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};

int n, m, mmp[MAXN][MAXN], dp[MAXN][MAXN];
bool prot[MAXN][MAXN];

inline int dfs(int x, int y) {
    if(prot[x][y]) return -1e9;
    if(dp[x][y] != -1) return dp[x][y];
    dp[x][y] = 1;
    for(int i = 0; i < 4; i++) {
        int nx = x + fix[0][i], ny = y + fix[1][i];
        if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
        if(mmp[x][y] > mmp[nx][ny]) dp[x][y] = std::max(dp[x][y], dfs(nx, ny) + 1);
    }
    return dp[x][y];
}

char op;
int a, b, c, d;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            mmp[i][j] = readint();
        }
    }
    m = readint();
    while(m--) {
        op = readop();
        if(op == 'Q') {
            int mx = 0;
            memset(dp, -1, sizeof(dp));
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    mx = std::max(mx, dfs(i, j));
                }
            }
            printf("%d\n", mx);
        } else if(op == 'C') {
            a = readint(); b = readint(); c = readint();
            mmp[a][b] = c;
        } else if(op == 'S') {
            a = readint(); b = readint(); c = readint(); d = readint();
            for(int i = a; i <= c; i++) {
                for(int j = b; j <= d; j++) {
                    prot[i][j] = true;
                }
            }
        } else {
            a = readint(); b = readint(); c = readint(); d = readint();
            for(int i = a; i <= c; i++) {
                for(int j = b; j <= d; j++) {
                    prot[i][j] = false;
                }
            }
        }
    }
    return 0;
}