编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 900ms

├ 测试数据 07：答案正确... 1400ms

├ 测试数据 08：答案正确... 1666ms

├ 测试数据 09：答案正确... 3556ms

├ 测试数据 10：答案正确... 3994ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：11516ms

险过！

program zha_meng;type node=record wh,zhi:longint; end;const maxn=1502;dx:array[1..2]of -1..1=(-1,1);var i,j,k,l,m,ffff,nn,n,sn,x,y,sj,sm,max,u,v:longint; c:array[0..maxn*maxn,0..2]of longint; a:array[0..maxn,0..maxn]of longint; heng,lie:array[0..maxn,0..4]of node; temp,xxxx:node; yes:boolean;procedure sort(l,r:longint);var i,j,x:longint;begin i:=l; j:=r; x:=c[(l+r)shr 1,0]; repeat while cx do dec(j); if ij;if l

Accepted 有效得分：100 有效耗时：4391ms

维护每行每列前4优的解

why?

lx大牛说的很清楚

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 228ms

├ 测试数据 07：答案正确... 322ms

├ 测试数据 08：答案正确... 494ms

├ 测试数据 09：答案正确... 1150ms

├ 测试数据 10：答案正确... 1353ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：3547ms

等待 waiting 队伍！！AC

算法很简单，先用每一朵花的花瓣数对花排序 记录： 原有位置 花瓣数 最大花朵数

开两个数组 分别保存每行前四大的花朵 和 每列前四大的花朵（最多三个点不能到达）

接下来从花瓣数最少的开始DP（每次对花瓣数相同的花进行）

1：先找它的上一行 下一行 前一列 后一列 中是否有更优解，然后更新

2：维护更新后的花所在行和列的前4大

扫描所有结点

从每行 每列的最大值中取最大 既答案！！

膜拜ORZ Cgy

虽然下滑了一点通过率,但是做了这题我又对DP有了新的见解,真是融会贯通啊!!!

Orz cgy

看了大牛的讲解深受启发

发题人说两句吧：

此题的基础算法时间复杂度为O(n^3)，可以勉强过5个点。

标程的算法貌似是保存每行每列的四个最优值……

讲得很模糊，cg4ever神牛讲的还算细致：

“按叶片数排序后来做

容易想到的是树状数组,一共开 4 * N 个大小是 N 的.

不过这样会造成MLE，更重要的是后两个点过不了.

而更优的解法是记录每行每列的最优的4个值,这样就可以过了。”

题目很难做，大家耐心做哦~

用递归做，但全错

附代码：

var a:array[1..1500,1..1500] of longint;

i,j,l,m,n,max:longint;

procedure ss(q,w,e,r:longint);

var f:longint;

begin

if (q>n) or (qn) or (w

OoRz Cgy

虽然算法不是原创的

但是发现我时间最短啊,4702MS

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 322ms

├ 测试数据 07：答案正确... 525ms

├ 测试数据 08：答案正确... 681ms

├ 测试数据 09：答案正确... 1462ms

├ 测试数据 10：答案正确... 1712ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4702ms

算法虽然是线性的

但常数实在太大

MAXN=1500

复杂度是O(MAXN*MAXN*4*4)

但是有不少取最大,更新步骤,时间就上去了

==试下保存3优的

Orz 神牛题！

好像在OIBH月刊上看到过

树状数组开4N发现过不了于是囧了。。

然后可以发现其实只要保存每行每列前4优即可。

总共写了500行。从C++到pas。。貌似N^2logn被我优化到极限了。。

我的天……最后俩数据太大了

站地下室吧