250 条题解
-
0
yuanjidan LV 4 @ 2009-08-17 18:15:54
(╰_╯)#
(╰_╯)#(╰_╯)#
(╰_╯)#(╰_╯)#(╰_╯)#
(╰_╯)#(╰_╯)#(╰_╯)#(╰_╯)#
题目怎么能这样！
我理解错了
！ -
0
交了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 9ans：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 9ans：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
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
如对本题有疑问可以参看我的题解：http://xujieqi.blog.hexun.com/35722312_d.html
-
0
xpaq.matrix LV 6 @ 2009-08-03 08:15:40
做了两天......太难了。。。。。处理数据总出错误，主要是题意理解问题，这道题说得不太清楚啊。
-
0
编译通过...
├ 测试数据 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
-
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
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
编译通过...
├ 测试数据 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)，汗！居然还过两个点……
yuanjidan
LV 4
@ 2009-08-17 18:15:54
