題目大意： 花花山峰巒起伏，峰頂常年被雪，Memphis打算幫花花山風景區的人員開發一個滑雪項目。 我們可以把風景區看作一個n*n的地圖，每個點有它的初始高度，滑雪只能從高處往低處滑【嚴格大於】。但是由於地勢經常變動【比如雪崩、滑坡】，高度經常變化；同時，政府政策規定對於每個區域都要間歇地進行保護， ...
題目大意：
花花山峰巒起伏，峰頂常年被雪，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
