数组开小了==

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

编译通过...

├ 测试数据 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

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

为什么我在自己的电脑上测就ac，在vijos上就错误号200?

这个不是个简单的动态么?= =

多进程DP，先直接从下面传上来，然后找到当前层最小的向左向右更新最优解。

时间复杂度 O(n^2)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

无敌简单

program test;

var n,i,j:word;

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

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

begin if a

有图吗？好难理解

最短路，我看还是算了吧，是稀疏图诶.

继承下面一层的值，然后处理一下第一个数和最后一个数，在左右扫一遍就行了。

Main Code：

for i:=n-1 downto 1 do

begin

for j:=1 to i do

f:=min(f,f)+data;

f:=min(f,f+data);

f:=min(f,f+data);

f:=min(f,f+data);

for j:=2 to i do

f:=min(f,f+data);

f:=min(f,f+data);

for j:=i-1 downto 1 do

f:=min(f,f+data);

end;

一定要细心....

我觉得比动态方程更重要的在这里

for i:=1 to n-1 do

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

for i:=1 to n do read(f[n,i]);

for i:=2 to n do f[n,i]:=f[n,i-1]+f[n,i];//从(1,1)开始做

方程把数字金字塔改一下就可以了....

(我觉得我的程序比下面两位大哥短得多......)

program sunzhiyong1006;

var a:array [1..1000,1..1000] of byte; b:array [1..4] of byte;

i,n,m,j,q,w:integer; min,k:byte;

procedure inset;

begin

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

for i:=1to n do

for j:= 1to i do

readln( a);

end;

procedure init(min,a:byte);

begin

if ji then a:=a;

b[1]:= a; b[2]:=a;

b[3]:=a; b[4]:=a;

for k:=1to 4do

if b[k]+a

v001]of longint;

n,i,j,kngint;ongint):l

min:=a

ifin:=b;

pr

eg

+1 to i d,ji,j];

i,1] then f+a;

fornj-1 do

if f,j] t]+a;

for j do

if f[i,i:=f+a;

if f[i,ithen f:=f+a;

for j:=+1 do

if f>f[i,jf[ii,j];

en;

bein

readln(n);

for i:=1 to n do

for j:=1 to i do begin

read(a);a:=a;

end;

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

for j:=2 to n do f[n,j]:=f[n,j-1]+a[n,j];

if f[n,n]>f[n,1]+a[n,n] then f[n,n]:=f[n,1]+a[n,n];

for j:=n-1 downto 2 do

if f[n,j]>f[n,j+1]+a[n,j] then f[n,j]:=f[n,j+1]+a[n,j];

for i:=n-1 downto 1 do begin

f:=min(f,f,f)+a;

f:=min(f,f,f)+a;

for j:=2 to i-1 do if ff then begin

minj:=j;mi:=f;

end;

if i>1 then scan;

end;

writeln(f[1,1]);

end.

├ Hint: 注意：每个点最多只有四个出发的方向，但不代表最多只有四个到达的方向！

program sunzhiyong1006;

var a:array [1..1000,1..1000] of byte; b:array [1..4] of byte;

i,n,m,j,q,w:integer; min,k:byte;

procedure inset;

begin

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

for i:=1to n do

for j:= 1to i do

readln( a);

end;

procedure init(min,a:byte);

begin

if ji then a:=a;

b[1]:= a; b[2]:=a;

b[3]:=a; b[4]:=a;

for k:=1to 4do

if b[k]+a

小岛的方法有误

向两边扫时不能用while

int key=f[i][1],k=1;

for(j=2;jf[i][mod(j-1,i)]+a[i][j])

f[i][j]=f[i][mod(j-1,i)]+a[i][j];

if(j==mod(k,i)) break;

}

C++的！！ 第一次写这么长的程序，没有一处错误，一遍AC，虽然速度慢了点。

我的网站正在建设：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

#define MIN(x,y) (x>y)?y:x

#define DP_N 2 //同层从最小点左右双向搜的次数

using namespace std;

int n,a[1001][1001],b[1001][1001],minNum,minI;

int main(){

int i,j,k;

cin>>n;

for(i=1;ia[i][j];

b[i][j]=a[i][j];

}

for(i=2;i

这什么破题，考语文呢？！

program v1006;

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

n,i,j,k,minj,mi:longint;

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

begin

min:=a;

if min>b then min:=b;

if min>c then min:=c;

end;

procedure scan;

begin

for j:=minj+1 to i do

if f>f+a then f:=f+a;

if f>f+a then f:=f+a;

for j:=2 to minj-1 do

if f>f+a then f:=f+a;

for j:=minj-1 downto 1 do

if f>f+a then f:=f+a;

if f>f+a then f:=f+a;

for j:=i-1 downto minj+1 do

if f>f+a then f:=f+a;

end;

begin

readln(n);

for i:=1 to n do

for j:=1 to i do begin

read(a);a:=a;

end;

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

for j:=2 to n do f[n,j]:=f[n,j-1]+a[n,j];

if f[n,n]>f[n,1]+a[n,n] then f[n,n]:=f[n,1]+a[n,n];

for j:=n-1 downto 2 do

if f[n,j]>f[n,j+1]+a[n,j] then f[n,j]:=f[n,j+1]+a[n,j];

for i:=n-1 downto 1 do begin

f:=min(f,f,f)+a;

f:=min(f,f,f)+a;

for j:=2 to i-1 do if ff then begin

minj:=j;mi:=f;

end;

if i>1 then scan;

end;

writeln(f[1,1]);

end.

编译通过...

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

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

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

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

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

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

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

为什么啊

很有语文味.....

害我WA了一次