题解:http://blog.163.com/syf_light_feather/blog/static/22375506720136288201186/?latestBlog

先不说那个诡异的提示，就说那从山的左下角出发，就是从山底出发的意思！哀！

求助啊

我和1294686601这位是一样的结果- -

var

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

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

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

begin

if a

读入之后，把能到达的点之间都连上边，跑一遍spfa，边权就是出发点的点权，设最上是1号点，d[1]+w[1]就是答案

注意，本行行尾可以到达本行及上一行的行首

编译通过... 

├ 测试数据 01：答案正确... (0ms, 49972KB) 

├ 测试数据 02：答案正确... (0ms, 49972KB) 

├ 测试数据 03：答案正确... (0ms, 49972KB) 

├ 测试数据 04：答案正确... (0ms, 49972KB) 

├ 测试数据 05：答案正确... (0ms, 49972KB) 

├ 测试数据 06：答案正确... (0ms, 49972KB) 

├ 测试数据 07：答案正确... (0ms, 49972KB) 

├ 测试数据 08：答案正确... (0ms, 49972KB) 

├ 测试数据 09：答案正确... (0ms, 49972KB) 

├ 测试数据 10：答案正确... (0ms, 49972KB) 

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

Accepted / 100 / 0ms / 49972KB 

#include

#include

#include

int find();

int mlong=0;

int temp[10];

using namespace std;

int main()

{

int i,j;

int high;

cin>>high;///获取山的高度

int moun[10][10];

for(i=0;imoun[i][j];

}

}

/////////////////////////////////////////////

for(i=0;i

这道题描述不靠谱阿……一定要注意本层的最后一段也可以到达上一层的第一段。这看起来是理所当然的，实际上却是本题描述的一个漏洞。

至于实现方面，可以先像普通数字三角形那样求出只考虑往上爬的最小路程，然后在本层内考虑同层的递推。注意两边的分别讨论。

此题关键就是对一层数据的处理 

环形结构求出所有点的最短路 可以使用循环+剪枝 

在环里某点 向左向右 若比原值小 就替换原值然后继续 否则就break 进入下一个点

本层数据处理完毕之后 可以使用标准DP扩展到高一层 然后继续进行环形短路

使用本方法 0ms 秒杀 代码c++ 只需40行~~~

├ 测试数据 01：答案正确... (0ms, 8036KB) 

├ 测试数据 02：答案正确... (0ms, 8036KB) 

├ 测试数据 03：答案正确... (0ms, 8036KB) 

├ 测试数据 04：答案正确... (0ms, 8036KB) 

├ 测试数据 05：答案正确... (0ms, 8036KB) 

├ 测试数据 06：答案正确... (0ms, 8036KB) 

├ 测试数据 07：答案正确... (0ms, 8036KB) 

├ 测试数据 08：答案正确... (0ms, 8036KB) 

├ 测试数据 09：答案正确... (0ms, 8036KB) 

├ 测试数据 10：答案正确... (0ms, 8036KB) 

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

Accepted / 100 / 0ms / 8036KB 

foo.pas(4,10) Warning: Function result does not seem to be set

foo.pas(12,10) Warning: Function result does not seem to be set

├ 测试数据 01：答案错误... (235ms, 8432KB)

├ 测试数据 02：答案错误... (235ms, 8432KB)

├ 测试数据 03：答案错误... (107ms, 8432KB)

├ 测试数据 04：答案错误... (126ms, 8432KB)

├ 测试数据 05：答案错误... (114ms, 8432KB)

├ 测试数据 06：答案正确... (122ms, 8432KB)

├ 测试数据 07：答案错误... (107ms, 8432KB)

├ 测试数据 08：答案错误... (118ms, 8432KB)

├ 测试数据 09：答案错误... (122ms, 8432KB)

├ 测试数据 10：答案正确... (122ms, 8432KB)

为啥我在自己点哪里测试数据全对，可是一提交就只对两个点呢？

求各位大牛的帮助，在下谢谢了！！

这种带环的DP可以采用循环DP。。说白了就是用一个无限循环不停的用已有的状态更新每一个状态直到所有状态值都不改变。。但是本题可以有更清晰的做法。。

本题对DP顺序的要求可谓极为严格。。对于每一层。。我们必须先更新两头。。再更新中间。。最后利用本层的状态更新上一层。。两头的顺序是（假设最底层为0层。。f[i][j]表示第i层第j段）：先用f[i][0]的状态更新f[i][n-i-1]。。再用f[i][n-i-1]的状态更新f[i][0]。。中间的顺序是：先用f[i][j]更新f[i][j+1]。。再**倒着**用f[i][j]更新f[i][j-1]。。更新上层的顺序就无所谓了。。只要保证f[i][0]能转移到f[n-i-2]。。f[i][n-i-1]能转移到f[0]就好了。。

下面说说为什么要采用这样的DP顺序。。对于左右转移的状态。。如果不能保证最左或者最右的状态值是最优的。。那么本层的每一个状态值都不能保证是最优的。。所以我们必须先保证两头的最优性。。故而优先转移两头的状态。。由于所有的值都是正数。。所以两头必然只有一头能更新另一头而不会出现两头循环更新对方的情况。。所以一遍判断足矣。。再来就是中间部分的更新。。这个比较明显了。。前面说过。。开始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

题目理解错了，WA了一次，郁闷。

用SPFA就可以了，看清题意。就能过

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

const

move:Array[1..4,0..1] of longint=((0,1),(0,-1),(-1,-1),(-1,0));

var

Q:Array[1..600000] of record

x,y:longint;

end;

T,f:Array[0..1001,0..1001] of longint;

b:Array[0..1001,0..1001] of boolean;

limit,n,xx,yy,x,y,head,tail,i,j:longint;

procedure insert(x,y,xx,yy:longint);

begin

if (T[xx][yy]>0) and (f[x][y]+T[xx][yy]

竟然还要来回走，

如果只来不回，第八组就要出问题

扫三遍相当于来回走，所以绝对不会造成最小费用的改变

用dt，倒推，在在每层第一段多考虑一下注意就行了

记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1750987 Accepted 100 From fatso1234321－

　 P1006 FPC VJ_MD5.com.cn 2009-11-19 15:23:07

From Sunnypig

晴天小猪历险记之Hill 晴天小猪历险记 系列

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最后一组数据是什么这么变态 大家能告诉我是哪里错了吗？

program zhu;

var f,a:array[-1..1000,-1..1000]of int64;

n,max,k:int64;

i,j,e:longint;

zhuan,change:boolean;

function best(x,y,z:integer):integer;

begin

if y

（**注意**：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。 这句话有问题

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

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

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

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

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

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

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

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

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

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

一遍AC 无需搜两遍

#include

using namespace std;

int a[1001][1001]={};

int b[1001][1001]={};

int d[1001][1001]={};

int n;

int main(){

int i,j,k,l,m;

scanf("%d",&n);

for(i=1;i