网站系统建设系广告经营者,广告设计公司起名字,用wordpress制作网站模板下载,广西建设网查询Description国际象棋是世界上最古老的博弈游戏之一#xff0c;和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想#xff0c;棋盘是一个8*8大小的黑白相间的方阵#xff0c;对应八八六十四卦#xff0c;黑白对应阴阳。而我们的主人公小Q#xff0c…Description国际象棋是世界上最古老的博弈游戏之一和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想棋盘是一个8*8大小的黑白相间的方阵对应八八六十四卦黑白对应阴阳。而我们的主人公小Q正是国际象棋的狂热爱好者。作为一个顶尖高手他已不满足于普通的棋盘与规则于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。小Q找到了一张由N*M个正方形的格子组成的矩形纸片每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘当然他希望这个棋盘尽可能的大。不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘当然不管哪种棋盘必须都黑白相间即相邻的格子不同色所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积从而决定哪个更好一些。于是小Q找到了即将参加全国信息学竞赛的你你能帮助他么Input第一行包含两个整数N和M分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵表示这张矩形纸片的颜色0表示白色1表示黑色。Output包含两行每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积第二行为可以找到的最大矩形棋盘的面积注意正方形和矩形是可以相交或者包含的。Sample Input3 31 0 10 1 01 0 0Sample Output46HINT对于20%的数据N, M ≤ 80 对于40%的数据N, M ≤ 400 对于100%的数据N, M ≤ 2000 唉又搞错了把m打成了n0ms就WA了第一个数据就错了 话说以前做过一道差不多的题叫做玉嶦宫 然后就直接用了它的模型 1 const2 maxn2020;3 var4 n,m,ans1,ans2:longint;5 a,s:array[0..maxn,0..maxn]of longint;6 7 function max(x,y:longint):longint;8 begin9 if xy then exit(x);
10 exit(y);
11 end;
12
13 function min(x,y:longint):longint;
14 begin
15 if xy then exit(x);
16 exit(y);
17 end;
18
19 procedure init;
20 var
21 i,j:longint;
22 begin
23 read(n,m);
24 for i:1 to n do
25 for j:1 to m do
26 read(a[i,j]);
27 for i:1 to m do
28 s[1,i]:1;
29 for i:2 to n do
30 for j:1 to m do
31 if a[i,j]a[i-1,j] then s[i,j]:s[i-1,j]1
32 else s[i,j]:1;
33 end;
34
35 var
36 w,h:array[0..maxn]of longint;
37 tot:longint;
38
39 procedure insert(x:longint);
40 var
41 k:longint;
42 begin
43 k:0;
44 while (tot0)and(h[tot]x) do
45 begin
46 inc(k,w[tot]);
47 ans1:max(ans1,sqr(min(h[tot],k)));
48 ans2:max(ans2,h[tot]*k);
49 dec(tot);
50 end;
51 inc(tot);
52 h[tot]:x;
53 w[tot]:k1;
54 end;
55
56 procedure work;
57 var
58 i,j:longint;
59 begin
60 for i:1 to n do
61 begin
62 tot:0;
63 for j:1 to m do
64 if (tot0)or(a[i,j]a[i,j-1]) then insert(s[i,j])
65 else
66 begin
67 insert(0);
68 tot:0;
69 insert(s[i,j]);
70 end;
71 insert(0);
72 end;
73 writeln(ans1);
74 writeln(ans2);
75 end;
76
77 begin
78 init;
79 work;
80 end. View Code 转载于:https://www.cnblogs.com/Randolph87/p/3615083.html
