题解 - Vijos

0

逆袭的烧饼 LV 4 @ 2009-08-15 10:28:00

交了N次之后终于过了

另外提醒一下楼下的路径似乎错了..怎么看都是28可俺算出也是27结果捣鼓好久自己输出路径才发现有问题

【

10

1

9 1

1 1 9

9 9 9 1

9 9 9 1 9

1 1 1 1 9 1

9 9 9 9 9 1 9

1 1 1 1 1 1 9 1

9 9 9 9 9 9 9 1 9

1 9 1 1 1 1 1 1 1 9

ans：27

大家可以这样看方便些：

　　　　 1

　　　　9 1

　　 1 1 9

　　 9 9 9 1

　　 9 9 9 1 9

　　1 1 1 1 9 1

9 9 9 9 9 1 9

1 1 1 1 1 1 9 1

9 9 9 9 9 9 9 1 9

1 9 1 1 1 1 1 1 1 9

路线：

　　　　 *

　　　　9 *

　　 * 1 9

　　 9 9 9 *

　　 9 9 9 * 9

　　* * *| * 9 *

9 9 9 9 9 * 9

* * *| * * *| 9 *

9 9 9 9 9 9 9 1 *

* 9 1 1 1 1 1 1 1 9

( 2009-8-13 19:45:30 ) 】

　　　　 *

　　　　9 *

　　 * 1 9

　　 9 9 9 *

　　 9 9 9 * 9

　　* * *| * 9 *

9 9 9 9 9 * 9

* * *| * * | 9 []多余的

9 9 9 9 9 9 9 1 * 这排走第一个或者最后一个都是一样的

* 9 1 1 1 1 1 1 1 9

0

chicken soup LV 8 @ 2009-08-13 19:45:30

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

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

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

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

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

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

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

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

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

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

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

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

交了3次才AC

第一次看

麻烦

不做

后来在同学的带动下做了

开始还坚信题目描述没漏洞

后来不得不BS作者

那个括号里的附加说明说少了

其实是双向的！

而且还漏了

总之：

1.每一层第1段可以到本层、上一层、下一层（待考证，八成可以）的最后一段

2.每一层最后一段可以到本层、上一层、下一层（待考证，八成可以）的第1段

我把这种走法通俗说为转移

总之大家好好研究这个数据

这个样例很有用！

10

1

9 1

1 1 9

9 9 9 1

9 9 9 1 9

1 1 1 1 9 1

9 9 9 9 9 1 9

1 1 1 1 1 1 9 1

9 9 9 9 9 9 9 1 9

1 9 1 1 1 1 1 1 1 9

ans：27

大家可以这样看方便些：

1

9 1

1 1 9

9 9 9 1

9 9 9 1 9

1 1 1 1 9 1

9 9 9 9 9 1 9

1 1 1 1 1 1 9 1

9 9 9 9 9 9 9 1 9

1 9 1 1 1 1 1 1 1 9

路线：

9 *
1 9
9 9 9 *
9 9 9 * 9
* * *| * 9 *
9 9 9 9 9 * 9
* * *| * * *| 9 *
9 9 9 9 9 9 9 1 *
9 1 1 1 1 1 1 1 9

0

fengwuliu LV 6 @ 2009-08-11 09:57:12

靠！我第一遍就90分，第10组老过不了。找了半天最后发现时最大值取得小了！！！！！！！！！抓狂！！！！！

0

风雨桥 LV 7 @ 2009-08-10 10:05:06

晕倒~

1

2 3

4 5 6

7 8 9 10

实质是这样的

1

2 3

4 5 6

7 8 9 10

8可以走到4或5，而不是4或6

理解题意很重要啊！~

我做的是自上而下DP DP每一层的时候再左右DP （特殊情况特殊处理）

我的程序96行大费周折而且这个程序还很胖

0

shiyantimu LV 5 @ 2009-08-09 16:12:09

var

n:longint;

a,f:array [0..1001,0..1001] of longint;

procedure putinto;

var

i,j:longint;

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to i do

begin

read(a);

f:=100000;

end;

readln;

end;

end;

procedure doit;

var

i,j : longint;

flag : boolean;

begin

f[1,0]:=a[1,1];

f[1,1]:=a[1,1];

f[1,2]:=a[1,1];

for i:=2 to n do begin

repeat

flag:=true;

f:=f;

f:=f;

for j:=1 to i do begin

if (f > f + a) then begin

f:=f + a;

flag:=false;

end;

if (f > f + a) then begin

f:=f + a;

flag:=false;

end;

if (f > f + a) then begin

f:=f + a;

flag:=false;

end;

if (f > f + a) then begin

f:=f + a;

flag:=false;

end;

end;

if flag then break;

until false;

end;

writeln(f[n,1]);

end;

begin

putinto;

doit;

end.

0

Ignited LV 7 @ 2009-08-08 02:26:59

恶题...

为什么大家最多的都只搜了4次,我搜了8次才过...

我得多做些dp的题.要不是大牛们说了双搜策略我还不会呢...

0

Glamic LV 9 @ 2009-08-03 21:58:27

严重鄙视该题。

很显然题目没说清楚：每层的最后一段也可以到上一层的第一段。

0

1s LV 10 @ 2009-08-03 17:55:58

如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html

0

xpaq.matrix LV 6 @ 2009-08-03 08:15:40

做了两天......太难了。。。。。处理数据总出错误，主要是题意理解问题，这道题说得不太清楚啊。

0

残阳销雪 LV 4 @ 2009-07-31 17:46:52

var

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

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

i,j,n,temp:integer;

function min(a,b:integer):integer;

begin

if b

0

xusc_2009 LV 9 @ 2009-07-28 13:54:46

得得意意的写上30行程序，然后发现自己数组开太小了……

白wa了一次阿

0

fs302 LV 8 @ 2009-07-26 15:56:29

牛们称为Easy DP，让我尝到了做vijos以来最苦的一次。硬生生地提交了6次。估计本题第10000就是我交的。

关键在从下往上的递推，就像测评提示的一样。这类递推要分好几类。尤其是首位与末位。首位还得注意由下行末位推来的，末位即注意由下行首位推来的，故对此有5种推法。

0

traitor LV 9 @ 2009-07-25 19:26:10

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Flag 　　Accepted

题号　　P1006

类型(?) 　　动态规划

通过　　1945人

提交　　9992次

通过率　　19%

难度　　2

虽然很早就想出来了，但是真正做的时候还是不小心WA了一次、、、

可怜我本来就不咋高的AC Rate....

0

董 LV 10 @ 2009-07-24 19:08:46

http://hi.baidu.com/%CB%D5%CC%DAsauterne/blog

0

zhangjian555 LV 8 @ 2009-07-22 11:28:56

多谢楼下好心人给的数据

program p1006;

var

n:longint;

a:array[1..1000,1..1000]of longint;

f:array[1..1000,1..1000]of longint;

function min(a,b:longint):longint;

begin

if a>b then min:=b else min:=a;

end;

procedure init;

var

i,j:longint;

begin

assign(input,'in.in');

assign(output,'p1006.out');

reset(input);

rewrite(output);

readln(n);

for i:=1 to n do

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

readln;

close(input);

f[n,1]:=a[n,1];

f[n,n]:=f[n,1]+a[n,n];

for i:=2 to n-1 do

f[n,i]:=f[n,i-1]+a[n,i];

for i:=n-1 downto 2 do

f[n,i]:=min(f[n,i+1]+a[n,i],f[n,i]);

end;

procedure work;

var

i,fg,k:longint;

begin

for k:=n-1 downto 1 do

begin

for i:=1 to k do

begin

if (ik)and(i1) then f[k,i]:=min(f[k+1,i],f[k+1,i+1])+a[k,i];

if i=k then

begin

f[k,i]:=min(f[k+1,i],f[k+1,i+1])+a[k,i];

f[k,i]:=min(f[k,i],f[k+1,1]+a[k,i]);

end;

if i=1 then

begin

f[k,i]:=min(f[k+1,i],f[k+1,i+1])+a[k,i];

f[k,i]:=min(f[k,i],f[k+1,k+1]+a[k,i]);

end;

end;

fg:=1;

for i:=2 to k do

if f[k,i]

0

ayqzwu110 LV 7 @ 2009-07-21 10:30:58

const

zy = trunc( 1e9 ) ;

var

map : array[ 0 .. 1000 , 0 .. 1000 ] of longint ;

f : array[ 0 .. 1000 , 0 .. 1000 ] of int64 ;

n : longint ;

procedure init ;

var

i , j : longint ;

begin

readln( n ) ;

for i := 1 to n do

for j := 1 to i do

read( map[ i , j ] ) ;

end ;

function minn( a , b : longint ) : longint ;

begin

if a > b then minn := b

else minn := a ;

end ;

procedure dp ;

var

i , j , l , r : longint ;

begin

for i := 0 to 1000 do for j := 0 to 1000 do f[ i , j ] := zy ;

f[ n , 1 ] := 0 ;

for i := n downto 1 do

begin

f[ i , 1 ] := minn( f[ i , 1 ] , f[ i , i ] + map[ i , i ] ) ;

for j := 2 to i do

f[ i , j ] := minn( f[ i , j ] , f[ i , j - 1 ] + map[ i , j - 1 ] ) ;

f[ i , i ] := minn( f[ i , i ] , f[ i , 1 ] + map[ i , 1 ] ) ;

for j := i - 1 downto 1 do

f[ i , j ] := minn( f[ i , j ] , f[ i , j + 1 ] + map[ i , j + 1 ] ) ;

for j := 1 to i do

begin

l := j - 1 ; if l = 0 then l := i - 1 ;

r := j ; if r = i then r := 1 ;

f[ i - 1 , l ] := minn( f[ i - 1 , l ] , f[ i , j ] + map[ i , j ] ) ;

f[ i - 1 , r ] := minn( f[ i - 1 , r ] , f[ i , j ] + map[ i , j ] ) ;

//writeln( i , ' ' , j ,' ' , f[ i , j ] , ' ' , l , ' ' , f[ i - 1 , l ] , ' ' , r , ' ' , f[ i - 1 , r ] );

end ;

end ;

writeln( f[ 1 , 1 ] + map[ 1 , 1 ] ) ;

end ;

procedure main ;

begin

init ;

dp ;

end ;

Begin

main ;

end .

0

wyc4662 LV 10 @ 2009-07-20 23:27:48

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

上下DP，再左右DP

开始(i,j)左下以为是(i-1,j-1)弄了半天才知道是(i-1,j)，汗！居然还过两个点……

0

木头 LV 4 @ 2009-07-20 21:48:01

var

i,j,n:longint;

a,f:array[1..1000,1..1000]of longint;

begin

read(n);

for i:=1 to n do

for j:=1 to n do

read(a);

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

for i:=1 to n do

for j:=0 to n do

begin

f:=f;

if (j>=1) and (f+a>f) then

f:=f+a[i];

end;

writeln(f[n,n]);

end.

0

lys_oson LV 8 @ 2009-07-19 20:32:13

数组开小了==

ac啊~

dp时要左右扫两边!!

var

n,i,j,k:longint;

a:array[1..1000,1..1000] of longint;

f:array[1..1000,1..1000] of longint;

function min(a,b:longint):longint;

begin if a1)and(j1 then f:=min(f,f+a);

if j=i then f:=min(f,f+a);

end;

for j:=i downto 1 do

begin

if j

0

695574648 LV 8 @ 2009-07-17 21:36:10

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

语文+2次动规=AC

注意每一次它都可以朝左、右、左上、右上四个方向走，在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段。这是与数字三角形的不同之处所在！

题解

249 条题解

晴天小猪历险记之Hill

信息

状态

开发

支持

题解

249 条题解

晴天小猪历险记之Hill

信息

状态

开发

支持

还没有账户？

登录