題目大意：
花花山峰巒起伏，峰頂常年被雪，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要作一次回答。 思路： 由於Q,S,B的次數只有100次，只要暴力做S,B，Q用記憶化搜索就行了。 代碼：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 inline char Nc(){
6 static char buf[100000],*p1=buf,*p2=buf;
7 if(p1==p2){
8 p2=(p1=buf)+fread(buf,1,100000,stdin);
9 if(p1==p2)return EOF;
10 }
11 return *p1++;
12 }
13 inline void Read(int& x){
14 char c=Nc(),b=1;
15 for(;c<'0'||c>'9';c=Nc())if(c=='-')b=-1;
16 for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());x*=b;
17 }
18 inline void Read(char& C){
19 char c=Nc();
20 for(;c<'A'||c>'Z';c=Nc());
21 C=c;
22 }
23 int i,j,k,n,m,a[701][701],a1,a2,a3,a4,f[701][701],Ans;
24 int x[4]={-1,1,0,0};
25 int y[4]={0,0,1,-1};
26 bool b[701][701];
27 char C;
28 inline void Dfs(int X,int Y){
29 for(int i=0;i<4;i++)
30 if(x[i]+X&&x[i]+X<=n&&y[i]+Y&&y[i]+Y<=n&&a[X][Y]>a[x[i]+X][y[i]+Y]&&!b[x[i]+X][y[i]+Y]&&f[X][Y]+1>f[x[i]+X][y[i]+Y]){
31 f[x[i]+X][y[i]+Y]=f[X][Y]+1;
32 Dfs(x[i]+X,y[i]+Y);
33 }
34 }
35 int main()
36 {
37 Read(n);
38 for(i=1;i<=n;i++)
39 for(j=1;j<=n;j++)
40 Read(a[i][j]);
41 Read(m);
42 while(m--){
43 Read(C);
44 if(C=='C'){
45 Read(a1);Read(a2);Read(a3);
46 a[a1][a2]=a3;
47 }else if(C=='S'){
48 Read(a1);Read(a2);Read(a3);Read(a4);
49 for(i=a1;i<=a3;i++)
50 for(j=a2;j<=a4;j++)
51 b[i][j]=1;
52 }else if(C=='B'){
53 Read(a1);Read(a2);Read(a3);Read(a4);
54 for(i=a1;i<=a3;i++)
55 for(j=a2;j<=a4;j++)
56 b[i][j]=0;
57 }else{
58 for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=1;
59 for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(!b[i][j]&&f[i][j]==1)Dfs(i,j);
60 for(Ans=0,i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]>Ans)Ans=f[i][j];
61 printf("%d\n",Ans);
62 }
63 }
64 return 0;
65 }
bzoj3208
