bzoj3208--记忆化搜索

2018-06-17 23:28:46来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目大意:

花花山峰峦起伏,峰顶常年被雪,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

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:EC笔记:第4部分:18、接口正确使用,不易被误用

下一篇:用C++实现的解数独(Sudoku)程序