编译通过...

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

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

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

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

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

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

标准DP的，囧。。。。。。。

考试时用搜索得50分，刚才打DP忘清零只得60。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var n,m,i,j,k:integer;

a:array[1..100,1..100] of integer;

f:array[0..100,0..200,0..100] of integer;

begin

readln(n,m);

for i:= 1 to n do

begin

for j:= 1 to m do

read(a);

readln;

end;

fillchar(f,sizeof(f),0);

for k:= 1 to n+m-1 do

for i:= 1 to n do

for j:= 1 to n do

begin

if (( i j ) and ((k-i) > 0) and ((k-j) >0)) then

begin

f := f;

if f < f then

f := f;

if f < f then

f := f;

if f < f then

f := f;

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

end;

end;

writeln(f[n-1,n+m-1,n]);

end.

如果有机会回到过去...

哎!

我测算的状态转移：

f=max(f,f,f,f)+a+a[j,k-j];

f表示在

行+列=k 时

经过第i行，第k-i个人；第j行，第k-j个人的最大值

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

可惜考后才有机会改正！！！

var n,m:longint;

a:array[0..101,0..51] of longint;

f:array[0..101,0..51,0..51] of longint;

procedure init;

var i,k:longint;

begin

readln(n,m);

fillchar(a,sizeof(a),0);

for i:=1 to n do

begin

for k:=1 to m do read(a);

readln;

end;

end;

function max(a,b,c,d:longint):longint;

begin

max:=a;

if max

其实我比赛的时候看错题了，但是最后我竟然稳定的AC了

这道题其实不用考虑相交，只要在相交的时候，相交的格子只取一次，就可以保证相交时得到的不是最优解。

不优化只有编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

囧~~~~~~~~~~~~~~~~~~

我明明用的是dp啊，比赛时只得了40分，现在竟然AC了，天啊

var

i,j,k,n,m:longint;

a:Array[0..50,0..50]of longint;

g:array[0..100,0..50,0..50]of longint;

function min(x,y:longint):longint;

begin

if x>y

then min:=y

else min:=x;

end;

function max(x,y,z,w:longint):Longint;

begin

if x>y

then max:=x

else max:=y;

if z>max

then max:=z;

if w>max

then max:=w;

end;

begin

readln(n,m);

for i:=1 to n do

begin

for j:=1 to m do

read(a);

readln;

end;

fillchar(g,sizeof(g),0);

g[1,1,2]:=a[1,2]+a[2,1];

for i:=2 to n do

g:=g+a+a;

for j:=2 to m do

g[j,1,2]:=g[j-1,1,2]+a[1,j+1]+a[2,j];

for k:=2 to n+m-2 do

for i:=1 to min(k,n-1) do

for j:=i+1 to min(k+1,n) do

begin

if (j=i+1)

then g[k,i,j]:=max(g[k-1,i-1,j-1],g[k-1,i-1,j],g[k-1,i,j],0)+a+a[j,k-j+2];

if (ji+1)

then g[k,i,j]:=max(g[k-1,i-1,j-1],g[k-1,i-1,j],g[k-1,i,j],g[k-1,i,j-1])+a+a[j,k-j+2];

end;

write(g[n+m-3,n-1,n]);

end.

动规 啊

考试没有想到啊

用搜索做的

0啊 ooO___|__

本菜题解：

http://hi.baidu.com/x50946702/blog/item/490bb93490aea21690ef3981.html

有详细flash

欢迎观看！感谢留言~！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第114人

动规万岁！！！！！！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次AC

囧～～考试的时候居然没时间做了

卡第二题上了～～省一就这么丢了，郁闷～～

***|Hpec killed P1493 with usp

搜索+剪枝=AC

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

头一回AC动态规划题,虽然没用动规....

第103名...知足了......

I hate....

如果，

忆………………

Flag 　　Accepted

题号 　　P1493

类型(?) 　　动态规划

通过 　　100人

提交 　　209次

通过率 　　48%

难度 　　2

t:=f[k-1,i,ii];

if (i-1>0)and(ii-1>0) then t:=max(t,f[k-1,i-1,ii-1]);

if (i-1>0)and(i-1ii) then t:=max(t,f[k-1,i-1,ii]);

if (ii-1>0)and(ii-1i) then t:=max(t,f[k-1,i,ii-1]);

f[k,i,ii]:=t+a+a[ii,jj];

经过本人的一次AC

终于成功把此题的AC率提高到0.5

庆祝

var

m,n,i,k,j,j1:longint;

a:array[0..200,0..200] of longint;

f:array[-2..102,-2..102,-2..102] of longint;

function max(x,y,z,c:longint):longint;

var

k:longint;

begin

k:=0;

if x>k then k:=x;

if y>k then k:=y;

if z>k then k:=z;

if c>k then k:=c;

max:=k;

end;

begin

read(m,n);

for i:=1 to m do

for j:=1 to n do

read(a);

for i:=1 to m+n-1 do

for j:=1 to n do

for j1:=1 to j do

begin

if ((j=j1)and(jn)and(j1n))or(j>i)or(j1>i)or(i-j+1>m)or(i-j1+1>m)or(i-j+1

经典原题，换汤不换药。。