题解

35 条题解

  • 1
    @ 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
    @ 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
    @ 2009-11-02 15:29:01

    强大

  • 0
    @ 2009-10-29 15:41:35

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

  • 0
    @ 2009-10-29 11:17:52

    Orz

    想了一个月才明白..

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

    正着就有好多种..

    我真是脑残

  • 0
    @ 2009-10-22 16:15:48

    。。

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

  • 0
    @ 2009-10-21 09:23:34

    我认为边界应该是:

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

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

  • 0
    @ 2009-10-19 11:55:11

    自卑啊,难度是0啊!!!!!!!!!!!!!!

    感谢大家

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

  • 0
    @ 2009-10-10 22:47:32

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

    多谢boyzkk牛的指导..

  • 0
    @ 2009-10-07 20:29:26

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

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

    故得名fillchar

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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解决

  • 0
    @ 2009-10-03 16:03:59

    突破思维障碍,倒着进行DP。

信息

ID
1661
难度
6
分类
动态规划 点击显示
标签
递交数
895
已通过
226
通过率
25%
被复制
2
上传者