f表示a[i]不移动，从第i个点到n的最小消耗值

f表示a[i]移动，从第i个点到n的最小消耗值

使用逆推

f可以由i+1是移动点和i+1不是移动点的来，所以f的转移方程式是：

f=min(f+abs(a[i]-a),f+abs(a[i]-a));

另外就是处理f，同样是可以由两种状态的来，i+1是移动点和i+1不是移动点

f=min(min(f[j,0]+abs(a[i]-a[j+1]),f[j,1]+abs(a[i]-a[j+2))+abs(a[i]-a[j])+sum[j]-sum);

sum[i]表示前i个节点不移动的前缀和

sum[j]-sum 相当于从i+2开始j结束累加所有差值

另外需要特殊处理j=n的情况，当j=n时

f:=min(f,sum[n]-sum+abs(a[i]-a[n]))

复杂度O(n^2)

初始化f=f=正无穷

f[n,0]=f[n,1]=0

注意f转移时，会出现i+2>n的情况，所以a[n+1]=a[n]

最后输出min(f[1,1],f[1,0])即可

readln(n);

for i:=1 to n do

begin

read(a[i]);

if i>1 then sum[i]:=sum+abs(a[i]-a);

end;

fillchar(f,sizeof(f),$7f);

a[n+1]:=a[n];

f[n,0]:=0;

f[n,1]:=0;

for i:=n-1 downto 1 do

begin

f:=min(f+abs(a-a[i]),f+abs(a[i]-a));

for j:=i+1 to n-1 do

if f>min(f[j+1,0]+abs(a[i]-a[j+1]),f[j+1,1]+abs(a[i]-a[j+2]))+abs(a[i]-a[j])

+sum[j]-sum then f:=min(f[j+1,0]+abs(a[i]-a[j+1]),f[j+1,1]+abs(a[i]-a

[j+2]))+abs(a[i]-a[j])+sum[j]-sum;

f:=min(f,sum[n]-sum+abs(a[i]-a[n]));

end;

writeln(min(f[1,1],f[1,0]));

我想 有时候dp状态好重要。。。
一开始 我这么转移 。。 dp[i][0] 表示i ... n 所需最小消耗体力 dp[i][1] 表示最小交换体力条件下第i个是为a[i+1] 还是a[i]

感觉转移得挺合理的。。等评测完我懵逼了 用了对拍后 发现这个状态的确是转移错了 有情况没有考虑进去
例如 dp[i][0] 有多个相等的答案 但是却只记录了一种
后来 改成 dp[i][0] 表示第i个不移动的最小消耗体力 dp[i][1]表示第i 个移动的最小消耗体力 TMD 。这下终于对了

测试数据 #0: Accepted, time = 0 ms, mem = 16988 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 16988 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 16988 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 16992 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 16988 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 16988 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 16988 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 16992 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 16988 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 16988 KiB, score = 10
Accepted, time = 30 ms, mem = 16992 KiB, score = 100

强大

不错的一题！提醒了我们注意正难则反。

Orz

想了一个月才明白..

倒着一个位置上就只有两种可能

正着就有好多种..

我真是脑残

。。

没考虑j=n的特殊情况40分。。

我认为边界应该是:

f[n][0] = 0; f[n][1] = Inf;

这样就不用A[n+1] = A[n] 了。

自卑啊，难度是0啊！！！！！！！！！！！！！！

感谢大家

貌似J=N-1也要特殊考虑

来了个新的评测机..然后我终于过了..

多谢boyzkk牛的指导..

LS。。fillchar的意思不是将每个都赋成后面那个值

而是一个字节一个字节填充

故得名fillchar

255就是一个字节填充满的值

sum[1]=0 sum[i]:=sum+abs(a[i]-a);

状态转移方程看LS

writeln(min(f[1,0],f[1,1]));

另：LS的应该是把F全都赋值成maxn吧 不是255吧

fillchar(f,sizeof(f),255);

f[n,0]:=0;

f[n,1]:=0;

a[n+1]:=a[n];

For i:=n-1 downto 1 do

begin

f:=Min(f+abs(a-a[i]),f+abs(a-a[i]));

For j:=i+1 to n-1 do

f:=Min(f,Min(f[j+1,0]+abs(a[i]-a[j+1]),f[j+1,1]+abs(a[i]-a[j+2]))+abs(a[i]-a[j])+sum[j]-sum);

f:=Min(f,sum[n]-sum+abs(a[i]-a[n]));

end;

for j:=i+1 to n-1 do

begin

f:=min(f,f[j+1,0]+abs(h[i]-h[j])+abs(h[i]-h[j+1])+sum[j]-sum);

f:=min(f,f[j+1,1]+abs(h[j+2]-h[i])+abs(h[i]-h[j])+sum[j]-sum);

end;{！！！！！！！！！！！}

f:=min(f,sum[n]-sum+abs(h[n]-h[i]));

这样全对

for j:=i+1 to n-1 do

begin

f:=min(f,f[j+1,0]+abs(h[i]-h[j])+abs(h[i]-h[j+1])+sum[j]-sum);

f:=min(f,f[j+1,1]+abs(h[j+2]-h[i])+abs(h[i]-h[j])+sum[j]-sum);

f:=min(f,sum[n]-sum+abs(h[n]-h[i]));

end;！！！！！！！！！！！！！！

这样70分

为什么？？？？？？

有区别么？？？

max[k][i][0]表示走到第k格，第K格放着的是第i的数据的最优解

max[k][i][1]表示走到第k格，第K+1格放着的是第i的数据的最优解

因为站着的和前一格中必会有一个存放着k+1的数据，所以可以用上述状态表示

DP方程：

max[k+1][k+1][0]=min(max[k+1][k+1][0],max[k][i][0]+abs(a[i]-a[k+1]));

if(k+2

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

如楼上们的牛所说。。。

题解 http://254117343.blog.163.com/

一不小心被人抢了先手。。。。

通过 　　101人 。。。。。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\___|_

一次Ac! Rp++.

经过仔细分析，发现问题实质是制造循环节使得置换后的体力消耗最少。由于前面的决策在先，子问题在后，因此划分阶段应该从后往前进行。f[i][j]表示从第i个位置往后所能构成的最小体力消耗，其中j=1为要进行置换，0则不需要。最后输出f[1][0]和f[1][1]中最小的那个数。f[i][0] = min{f[k][1]+sum+abs(a[k-1]-a[i])+abs(a[k+2]-a[i]),f[k][0]+sum[k]+abs(a[k+1]-a[i])+abs(a[k+1]-a[i])) f[i][0] = min{f[0]+abs( a-a[i]), f[1]+abs( a-a[i]). sum为预先计算的部分和。小细节：a[n+1]=a[n]。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我靠第一次忘记写

IF I>1 了 直接就SUM:=SUM+ABS(A-A)

编译通过...

├ 测试数据 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, 足见我傻×.

我的方法和大家完全不一样...不过容易想(不容易实现)

f[i][j]表示走到调整后的第i段路. 调整后第i段路是原来的第j段路的最小费用.

注意到任意的调整都能被表示成循环.

所以整个调整后的序列就是若干个循环的组成.

因此, f[i][j] = min(f[j - 1][k] + cost).

朴素的复杂度是O(N^3).

但是有优化, g[i]表示min(f[i - 1][j] + abs(a[i + 1] - a[j]));

就优化到了O(N^2).

另外注意, 若一个循环是一个数的话要特殊处理, 我又弄了个h数组.

编译通过...

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