「BZOJ3208」花神的秒题计划Ⅰ
Description
背景「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要作一次回答。
花神一看，这不是超简单！立刻秒出了标算~
Input
第一行n，第二行开始n*n的地图，意义如上；接下来一个m，然后是m个命令，如上
Output
对于每一个Q输出单独一行的回答
Sample Input
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 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
Sample Output
24
3
3
样例解释：
第一个Q路线为：25->24->23->22….->3->2
第二个Q的路线为：10->9->2
HINT
100%的数据：1<=n<=700;1<=m<=1000000;其中Q、S、B操作总和<=100;
题中所有数据不超过2*10^9
题解
暴力暴力暴力
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 1000000007 using namespace std; #define p(i,j) (i-1)*m+j int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; int a[705][705],f[705][705]; bool forb[705][705]; void change(int x,int y,int val) { a[x][y]=val; } void mark(int a,int b,int c,int d,bool f) { for(int i=a;i<=b;i++) for(int j=c;j<=d;j++) forb[i][j]=f; } int dp(int x,int y) { if(forb[x][y])return -inf; if(f[x][y]!=-1)return f[x][y]; f[x][y]=1; for(int i=0;i<4;i++) { int tx=x+xx[i],ty=y+yy[i]; if(tx<1||ty<1||tx>n||ty>n)continue; if(a[x][y]>a[tx][ty])f[x][y]=max(f[x][y],dp(tx,ty)+1); } return f[x][y]; } int main() { n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=read(); int a,b,c,d; m=read(); while(m--) { char ch[2]; scanf("%s",ch+1); if(ch[1]!='Q') { a=read();b=read();c=read(); } if(ch[1]=='C')change(a,b,c); if(ch[1]=='B')d=read(),mark(a,c,b,d,0); if(ch[1]=='S')d=read(),mark(a,c,b,d,1); if(ch[1]=='Q') { int mx=0; memset(f,-1,sizeof(f)); for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) mx=max(mx,dp(j,k)); printf("%d\n",mx); } } return 0; } |
Subscribe
计数器 9856793
OI 课件=>
OI 课件=>