题解 - Vijos

1

搬运工 (syrth0p1) LV 10 @ 2025-10-14 19:33:49

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string>
#include<map>
#include<cstring>
#include<vector>
#define inf 1e9
#define ll long long
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Dow(i,j,k) for(int i=k;i>=j;i--)
using namespace std;
int f[5001][2],a[5001],n,sum[5001];
int main()
{
    scanf("%d",&n);
    For(i,1,n)
        scanf("%d",&a[i]),sum[i]=sum[i-1]+(i==1?0:1)*abs(a[i]-a[i-1]);
    a[n+1]=a[n];
    For(i,1,n*2)    f[i][1]=f[i][0]=inf;
    f[n][1]=f[n][0]=0;
    Dow(i,1,n-1)
    {
        f[i][0]=min(f[i+1][1]+abs(a[i+2]-a[i]),f[i+1][0]+abs(a[i+1]-a[i])); 
        For(j,i+1,n-1)
            f[i][1]=min(f[i][1],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[i+1]);
        f[i][1]=min(f[i][1],sum[n]-sum[i+1]+abs(a[i]-a[n]));
    }
    printf("%d\n",min(f[1][1],f[1][0]));
}

1

zhqc LV 9 @ 2009-10-10 23:22:14

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]));

0

651291702@qq.com LV 8 @ 2016-09-18 21:01:10

我想有时候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

0

syl8er LV 8 @ 2009-11-02 15:29:01

强大

0

fs302 LV 8 @ 2009-10-29 15:41:35

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

0

honghaijie LV 9 @ 2009-10-29 11:17:52

Orz

想了一个月才明白..

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

正着就有好多种..

我真是脑残

0

hfl LV 8 @ 2009-10-22 16:15:48

。。

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

0

lc_jack LV 9 @ 2009-10-21 09:23:34

我认为边界应该是:

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

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

0

wll969 LV 8 @ 2009-10-19 11:55:11

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

感谢大家

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

0

Aries_C LV 9 @ 2009-10-10 22:47:32

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

多谢boyzkk牛的指导..

0

ymfoi LV 8 @ 2009-10-07 20:29:26

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

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

故得名fillchar

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

0

K-Boy LV 10 @ 2009-10-06 10:11:15

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

状态转移方程看LS

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

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

0

11022908 LV 9 @ 2009-10-05 18:38:45

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;

0

明慧 LV 10 @ 2009-10-04 20:57:33

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分

为什么？？？？？？

有区别么？？？

0

5162800 LV 9 @ 2009-10-04 20:33:32

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

0

lgxcgd LV 10 @ 2009-10-04 16:49:55

编译通过...

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

0

strini LV 8 @ 2009-10-04 11:26:38

编译通过...

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

0

prince_hao LV 10 @ 2009-10-03 22:39:08

编译通过...

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

0

boyzkk LV 10 @ 2009-10-03 21:07:57

编译通过...

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

0

OIWinner LV 10 @ 2009-10-03 17:38:06

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

DP解决

题解

36 条题解

旅行-2

信息

状态

开发

支持

题解

36 条题解

旅行-2

信息

状态

开发

支持

还没有账户？

登录