ls的程序着实精简，不过有个地方容易引起误会，他的l应该是步数+1

不过这样程序写出来十分好看

for m:=1 to n do

if m in then f:=f+a[m,l-m];

这句话我参考了………

要是再早一年做这题...

我早就光荣退休了.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一定要细心

44%

↑

↑

↑

↑

↑

↑

↑

↑

43%

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var f:array[-41..41,-41..21,-41..21,-41..21]of longint;

a:array[-41..21,-41..21]of integer;

i,j,k,l,dep,n:longint;

function max(q,w,e,r,t,y,u,i:longint):longint;

begin

if q>w then max:=q else max:=w;

if e>max then max:=e;

if r>max then max:=r;

if t>max then max:=t;

if y>max then max:=y;

if u>max then max:=u;

if i>max then max:=i;

end;

begin

readln(n);

for i:=1 to n do for j:=1 to n do read(a);

for dep:=2 to 2*n do

for j:=1 to n do

for k:=1 to n do

for l:=1 to n do

begin

f[dep,j,k,l]:=max(f[dep-1,j,k,l],

f[dep-1,j,k,l-1],

f[dep-1,j,k-1,l],

f[dep-1,j,k-1,l-1],

f[dep-1,j-1,k,l],

f[dep-1,j-1,k,l-1],

f[dep-1,j-1,k-1,l],

f[dep-1,j-1,k-1,l-1]);

if (j=k)and(k=l) then

f[dep,j,k,l]:=f[dep,j,k,l]+a[j,dep-j]

else if j=k then

f[dep,j,k,l]:=f[dep,j,k,l]+a[j,dep-j]+a[l,dep-l]

else if k=l then

f[dep,j,k,l]:=f[dep,j,k,l]+a[j,dep-j]+a[l,dep-l]

else if j=l then

f[dep,j,k,l]:=f[dep,j,k,l]+a[j,dep-j]+a[k,dep-k]

else f[dep,j,k,l]:=f[dep,j,k,l]+a[j,dep-j]+a[k,dep-k]+a[l,dep-l];

end;

write(f[2*n,n,n,n]);

end.

四维一次AC

重温此题，使用了费用流解法，一遍AC了……

p.s. 一开始程序一直死循环，看了半天才发现少了一个p:=p^.next，囧……

程序比较复杂，思路比较简单，可以看奥赛经典234页，讲得很详细。

当年看到这题什么话都说不出来……被吓怕了……现在看了JerryZhou的提示……猛然醒悟，感谢JerryZhou，这才是真正好的题解

多进程DP。

用4维做。。

27行可以AC。。

关键是转移方程。。

要考虑8种情况。。

to curmit大牛:

我simplex写了300+行然后毫无疑问的WA了.欧啊啊啊啊...

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111次AC

费用流可以k取方格数

最大费用最大流编了100行。

然后一遍AC，哈哈哈哈哈哈哈！！！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

状态转移方程是f[t,i,j,k]=max(f[t-1,i-1,j,k],f[t-1,i,j-1,k],f[t-1,i,j,k-1],f[t-1,i-1,j-1,k],f[t-1,i-1,j,k-1],f[t-1,i,j-1,k-1],f[t-1,i-1,j-1,k-1])+map+map[j,t-j+1]+map[k,t-j+1];

(t-n+1

以步数划分阶段，一定要开到39；

建议用一个循环来解决转移状态的问题。

哪位大牛说下初始状态和最终答案应该是什么？

还是有点迷糊......

.....................................

今年省赛第三题太顶歇了！！

囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧囧 囧囧

囧 囧囧囧囧囧囧囧囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧 囧 囧 囧

囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧囧

小優化：

AAABBBB

AABBBBB

ABBBBBB

BBBBBBA

BBBBBAA

BBBBAAA

前三排和后三排(A)肯定取完。所以階段循環只需要從4到2*n-4就行了。

又因爲N>=4，啊哈，正好不用特殊處理

最後把所有A位置的數加上去就行了。