实践证明——的确很easy！

我和楼下牛们的思路有些不一样:

f[i][j][k]表示：第一辆车到达i，第二辆车到达j，第三辆车到达k时的最小距离。

（并不一定i

数据太弱

鉴定完毕

AC 标程，仅供参考。

谢谢。

编译通过...

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

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

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

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

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

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

program P1547;

const

mm =2139062143;

var

ans :array[1..100,1..100,1..100]of longint;

n,i,j,k,l,max :longint;

dis :array[1..100,1..100]of longint;

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

begin

if (a>=b) and (a>=c) then exit(a);

if (b>=a) and (b>=c) then exit(b);

if (c>=b) and (c>=a) then exit(c);

end;

procedure search(a,b,c:longint);

var

i,j :longint;

begin

i:=maxin(a,b,c);

if (i=n) and (ans[a,b,c]ans[a,b,c]+dis[a,i+1]) then begin ans:=ans[a,b,c]+dis[a,i+1]; search(i+1,b,c); end;

if (ans[a,i+1,c]>ans[a,b,c]+dis) then begin ans[a,i+1,c]:=ans[a,b,c]+dis; search(a,i+1,c); end;

if (ans[a,b,i+1]>ans[a,b,c]+dis[c,i+1]) then begin ans[a,b,i+1]:=ans[a,b,c]+dis[c,i+1]; search(a,b,i+1); end;

end;

begin

readln(n);

for i:=1 to n do

for j:=i+1 to n do read(dis);

fillchar(ans,sizeof(ans),127); max:=maxlongint;

ans[1,1,1]:=0;

search(1,1,1);

writeln(max);

end.

樓下的做法就對，但是把W數組從-2開willy很不理解。

不知道自己写的算不算Dp，望大家指点

program xing;

var

w:array[-2..100,-2..100] of longint;

f:array[1..100] of longint;

v:array[1..100] of integer;

i,j,min,n,l:longint;

begin

readln(n);

for i:=1 to n-1 do begin

for j:=i+1 to n do

read(w);

readln;

end;

v[1]:=3;

for i:=2 to n do begin

min:=maxlongint;

l:=0;

for j:=1 to i-1 do

if (w[j,i]0) and (v[j]>0) and (w[j,i]

才4个数据……

DP乱搞搞就AC了……

忘记初始化了，样例输出2

赋值为maxlongint才过

我是这么写的。AC0MS

呃 为什么改了题解 我就是最后一个写题解的人了

编译通过...

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

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

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

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

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

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

dp[i][j][k]表示三台车子所在位置， 降序排列。

那么dp[i][j][k]=dp[m][j][k]+d[m][j+1]+d[j+1][J+2]+...+d[i];

d[j+1][J+2]+...+d[i] 这部分可以写函数dis(J+1,i)。

关键代码：

if(m

编译通过...

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

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

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

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

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

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

f[i][j][k] : 最快的车在i城市,第二快的在j城市,第三快的在k城市的最小费用。

个人认为题目较难理解!

我的做法和WJ的做法一样,虽然过得了,可是好像有反例:

6

1 1 1 2 33

1 33 33 33

33 33 33

33 33

1

自己的程序输出为69,而正确答案应该是38.

解释:第一辆车:1-2-3,总路程为2.

第二辆车:1-4,总路程为33.

第三辆车:1-5-6,总路程为3.

所以最优的方案应该是38.

初学者,请教问题:

第I行,有I-1个数 是"第2行,有1个数"的意思吗?

但样例中第2行有4个数,不知如何理解?

是否是这样的意思:第I行,有N-I+1个数?

枚举每一个城市

将所有含有上一城市的状态进行递推

最后寻找含有最后一城市的最小值输出

个人感觉楼下的做法相当妙..

比用三维数组的做法好很多..

用f[i]表示去前i个城市的最短距离，v[i]表示第i个城市当前的车的数量，初始时，

v[1]=3，状态方程就是f[i]:=f+min(a[j,i]),{j:=1 to i-1},另外注意一下数组v的处理就可以了，只有当一个城市有车时才能前往下一个城市！

总感觉自己的程序不太完善，不过还是能AC。。。数据弱?

3维的如何做啊

水。。。。

很简单啊,哪来的3维DP,我用很基础的DP就A啦

编译通过...

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

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

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

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

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

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

雅婷的通过率挺高嘛

在座的都是大牛啊（除了饿）……我也看看

看懂了！

所有人从1市出发，共三辆车

第一辆车去2市（路程1）

第二辆车去3市（路程1）

第三辆车去4市（路程1）

突然发现，还有一个市没去！

题目说不走回头路（不能从2、3、4市直接回到一市）

只好从2、3、4市中任选一辆开往五市（路程都是33）

33+1+1+1=36

完美解决

原来是这个意思...

标题好强的说