扫了4遍.....

题目好难理解啊！！

由上往下推比较爽。

label 1;

begin

1:goto 1;

end.

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

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

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

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

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

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

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

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

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

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

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

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

从左边可以走到右边

左上走到右下

右上走到左下

我将它当成是数字金字塔

倒是高级版的，所以越写越舒服

然后忘乎了，忘记了1+1>1

所以时间复杂度弄成了O(N^3) = =!

不过感觉扫描10来遍应该也行吧，我扫描了16遍

方程很简单 = =！

编译通过...

├ 测试数据 01：答案错误...程序输出比正确答案长

├ 测试数据 02：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 03：答案错误...

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

　├ 错误行输出

├ 测试数据 04：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 05：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 07：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

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

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

请问啥是存取非法

类似的题目 小胖办证

两次动态规划 数字三角形 环形结构

复杂边界 滚动数组 无后效性 转图最短路.?

两次动态规划

1- 数字三角形

第一次十分类似Usaco上的数字三角形…不同的是两边变的更加复杂..

很容易出错…因为虽然每一个格子只会有2个到达方向，而因为层数不断增加

边界的两个格子会有3个方向可以到达…

因此这里的更新可以有两种方法

for j:=2 to i do

beginn

updata(j,j-1);

updata(j,j);

end;

updata(1,1);updata(1,i);

updata(i+1,i);updata(i+1,1);

或者

for j:=2 to i-1 do

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

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

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

2- 环形结构

不同于小胖办证，这一题的模型类似一个圆锥体，同一层之间是环形结构，

对于前者只需要

for j:=2 to n do

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

for j:=n-1 downto 1 do

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

两边扫描一下就可以了…

我一开始确实想复杂了…

认为需要从每一个点开始往两边逐一扫描一下…

或者不断的扫描直到无法更新，这样都是不太好的..

可以用类似前者的作法，找出最小的点向两边扫描一遍..

key:=d;k:=1;

for j:=2 to i do

if dd+a do

begin

d:=d+a;

j:=c(j-1)

end;

j:=c(k+1);

while d>d+a do

begin

d:=d+a;

j:=c(j+1);

end;

一开始churchill说他扫2遍过不了，扫了20遍，我笑他。自己做时扫两边，结果20分，只过了（6，10），不知道为什么。后来改20遍AC了，还是不知道为什么。

编译通过...

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

秒杀，这题是数字金字塔的变形，多了可以同层内移动的方法，因此动规公式要考虑到同层内移动，用数字金字塔的方法继承上一层变量，然后对第一和最后一个数字进行分别处理，接着就AC了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀～～

DP好想但不好写～～需要讨论几种情况

用SPFA写会简单很多～～时间复杂度也差不多～求解的时间是O（E）=O（N）

如果想练习DP的话可以用DP做～～

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

先是只扫了2遍

20分（6，8）点过了

后来改成4遍

20分

改成6遍

60分

最后改成20遍

90分

原来初值设成了maxint！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

原来扫的过程也有讲究啊,每次从一行里取最小的,然后从这个同时左右开始扫...

状态里可以看到我的6次20分,我的ac率啊.....

每层先转移下面的，然后从左向右扫一遍，再从右向左扫一遍就AC了。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

看清题就不难了..每层最多4次DP

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我是第1500个过的，一直不理解

I层的第1个可以由I+1的第1个 或 I+1层的第I+1个 或I层的第I个 走来（反之I层第I个）

交了N次！！！！！！！！

献上我的bellman，楼下的SPFA千万别撞墙~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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;

{for i:=1 to n do begin

for j:=1 to i do write(f:3);

writeln;

end;

for i:=1 to n do begin

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

writeln;

end;}

writeln(f[1,1]);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Spfa原来可以很快。

构图，然后应用Dijkstra(最小堆实现)即可解决。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

#include

#include

#include

#define INF 1500000000

#define maxn 500500

#define maxcnt 1000

#define NUM(i,j) ((i)*((i)-1)/2+j)

struct Node{long num;struct Node *next;} *Adj[maxn+10];

long n,cost[maxn+10],ans,dist[maxn+10],find_out[maxn+10],heap[maxn+10],turn[5][2],heap_size;

void decrease_key(long i,long key)

{

　　long parent_i,tmp;

　　assert(key>1;

　　while(i>1 && dist[heap[parent_i]]>dist[heap[i]])

　　{

　　　　find_out[heap[i]]=parent_i;

　　　　find_out[heap[parent_i]]=i;

　　　　tmp=heap[i],heap[i]=heap[parent_i],heap[parent_i]=tmp;

　　　　i>>=1;

　　　　parent_i=i>>1;

　　}

}

void minheapify(long i)

{

　　long l,r,min,tmp;

　　l=i

烦完去了，交了两次，都没有写 readln(n);

搞得全部输出0 又不知道什么回事