52 条题解
-
0
raoyu LV 9 @ 2009-08-07 22:48:39
用A表示棋盘
对于正方形，可以类似于盖房子的模型
F=Min(F,F,F)+1
条件为 (Not(A Xor A))And(A Xor A)And(A Xor A)
即满足黑白相间的要求
对于矩形，可以利用极大化思想
F=H[J]*(R[J]-L[J]+1)
其中H[J]表示A向上最多可以延伸的高度，L[J],R[J]表示向左、右可以延伸的宽度
求L的代码如下
L[1]:=1;
For J:=2 to M do
Begin
L[J]:=J;
While(L[J]>1)And(H[J] -
0
EZ_ray040123 LV 10 @ 2009-07-31 12:12:07
用悬线法的可以不开2000*2000的数组
开2000*1的就可以了
一行行地dp -
0
现将原矩阵转换成一个新的矩阵，对于每一对(i,j)，当i>1且j>1时判断(i,j)和(i-1,j)(i,j-1)(i-1,j-1)是否相见，如果是，在新矩阵的(i-1,j-1)位置填充一个1，否则是0。
然后问题就变成了在新矩阵中找一个长宽为(x,y)的全是1的矩形（正方形），使(x+1)*(y+1)最大。
对于正方形，可以用一个DP解决。
对于矩形：参见WC2003王知昆的论文，使用极大化思想解决。
至此，时间复杂度为O(mn)，空间复杂度为O(mn)，但是常数有点大了……因此：
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 41ms
├ 测试数据 07：答案正确... 244ms
├ 测试数据 08：答案正确... 181ms
├ 测试数据 09：答案正确... 494ms
├ 测试数据 10：答案正确... 462ms -
0
tangdongjian LV 8 @ 2009-03-21 21:11:37
最大正方形：
int[2000][2000] C++ 开不了
我发现总是只有n+m-1个保存的数据在接下来的递推中要用
且每('\'方向的)斜线上恰有一个
我只开int[4000]
其中f[i]表示第i条('\'方向的)斜线上的要用数据最大矩形：
分治法
把一个矩形割成两个递归，然后处理横跨分割线的子矩形 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 478ms
├ 测试数据 07：答案正确... 900ms
├ 测试数据 08：答案正确... 1744ms
├ 测试数据 09：答案正确... 5244ms
├ 测试数据 10：答案正确... 681ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：9047ms
很无耻的过了。。 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案错误...
├ Hint: 恩,900*1200
├ 标准行输出
├ 错误行输出
├ 测试数据 07：答案正确... 447ms
├ 测试数据 08：答案正确... 338ms
├ 测试数据 09：答案错误...
├ Hint: 超越极限的2000*2000
├ 标准行输出
├ 错误行输出
├ 测试数据 10：答案正确... 759ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：80 有效耗时：1544ms...09和06死活过不去...拼了...
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 181ms
├ 测试数据 07：答案正确... 697ms
├ 测试数据 08：答案正确... 541ms
├ 测试数据 09：答案正确... 1166ms
├ 测试数据 10：答案正确... 1228ms
---|---|---|---|---|---|---|---|-Accepted 有效得分：100 有效耗时：3813ms
先预处理，搞好每个点往上，往左，往右能走的最长位置。再一列一列做，记下在每个点最往上延伸的前提下，往左走的最远距离和往右走的最远距离，更新答案就可以了。
-
0
razhangwei1 LV 3 @ 2008-09-12 15:14:45
真是太奇怪了，为什么同样是2000*2000的longint类型，我前6个点就AC，后面就超内存。。。。。。。。。。。。。。。。。
-
0
zyffyz8002 LV 3 @ 2007-11-06 22:53:32
哎……
还真是不公平啊……
c里面根本就没有boolean那么小的数据类型……
raoyu
LV 9
@ 2009-08-07 22:48:39
