/ Vijos / 题库 / 旅行 /

题解

49 条题解

  • 2
    @ 2017-03-25 10:30:11

    #include <iostream>
    #include <memory.h>
    #include <cstdio>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <list>
    #include <set>
    #include <iomanip>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <algorithm>
    using namespace std;
    long long i,a[100005],n,ans;
    int main()
    {
    while(cin>>n)
    {
    ans=0;
    for(i=0;i<n;i++) cin>>a[i];
    for(i=1;i<n-1;i++)
    {
    if(a[i]>a[i-1]&&a[i]>a[i+1])
    {
    ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
    a[i]=max(a[i-1],a[i+1]);
    }
    else if(a[i]<a[i-1]&&a[i]<a[i+1])
    {
    ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
    a[i]=min(a[i-1],a[i+1]);
    }
    }
    for(i=1;i<n;i++) ans=ans+abs(a[i]-a[i-1]);
    cout<<ans<<endl;
    }
    system("pause");
    return 0;
    }

  • 2
    @ 2017-03-25 10:26:27

    #include <iostream>
    #include <memory.h>
    #include <cstdio>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <list>
    #include <set>
    #include <iomanip>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <algorithm>
    using namespace std;
    long long i,a[100005],n,ans;
    int main()
    {
    while(cin>>n)
    {
    ans=0;
    for(i=0;i<n;i++) cin>>a[i];
    for(i=1;i<n-1;i++)
    {
    if(a[i]>a[i-1]&&a[i]>a[i+1])
    {
    ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
    a[i]=max(a[i-1],a[i+1]);
    }
    else if(a[i]<a[i-1]&&a[i]<a[i+1])
    {
    ans=ans+min(abs(a[i+1]-a[i]),abs(a[i-1]-a[i]));
    a[i]=min(a[i-1],a[i+1]);
    }
    }
    for(i=1;i<n;i++) ans=ans+abs(a[i]-a[i-1]);
    cout<<ans<<endl;
    }
    system("pause");
    return 0;
    }

  • 0
    @ 2014-11-05 01:10:30

    P1615旅行
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1615 旅行
    递交时间 2014-11-05 01:09:27
    代码语言 C++
    评测机 VijosEx
    消耗时间 193 ms
    消耗内存 672 KiB
    评测时间 2014-11-05 01:09:29

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 668 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 668 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 668 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 672 KiB, score = 10

    测试数据 #4: Accepted, time = 31 ms, mem = 672 KiB, score = 10

    测试数据 #5: Accepted, time = 23 ms, mem = 668 KiB, score = 10

    测试数据 #6: Accepted, time = 31 ms, mem = 672 KiB, score = 10

    测试数据 #7: Accepted, time = 31 ms, mem = 672 KiB, score = 10

    测试数据 #8: Accepted, time = 31 ms, mem = 672 KiB, score = 10

    测试数据 #9: Accepted, time = 31 ms, mem = 672 KiB, score = 10

    Accepted, time = 193 ms, mem = 672 KiB, score = 100

    代码

    #include <iostream>
    #include <cmath>
    #include <stdio.h>
    #include <algorithm>

    using namespace std;

    int a[100000 + 2];
    int n;
    int i;
    unsigned long long ans;

    int abs( int a )
    {
    if( a > 0 )
    return a;
    return -a;
    }

    int main()
    {
    while( scanf( "%d" , &n ) != EOF )
    {
    ans = 0;
    for( i = 0 ; i < n ; i++ )
    scanf( "%d" , &a[i] );
    for( i = 2 ; i < n ; i++ )
    if( a[i - 2] < a[i - 1] && a[i - 1] > a[i] )
    {
    ans += a[i - 1] - max( a[i - 2] , a[i] );
    a[i - 1] = max( a[i - 2] , a[i] );
    }
    else if( a[i - 2] > a[i - 1] && a[i - 1] < a[i] )
    {
    ans += min( a[i - 2] , a[i] ) - a[i - 1];
    a[i - 1] = min( a[i - 2] , a[i] );
    }
    for( i = 1 ; i < n ; i++ )
    ans += abs( a[i] - a[i - 1] );
    cout << ans << endl;
    }
    return 0;
    }

    weak!

  • 0
    @ 2014-11-03 23:20:20

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 952 KiB, score = 10

    测试数据 #1: Accepted, time = 7 ms, mem = 952 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 948 KiB, score = 10

    测试数据 #3: Accepted, time = 15 ms, mem = 952 KiB, score = 10

    测试数据 #4: Accepted, time = 328 ms, mem = 948 KiB, score = 10

    测试数据 #5: Accepted, time = 328 ms, mem = 952 KiB, score = 10

    测试数据 #6: Accepted, time = 343 ms, mem = 944 KiB, score = 10

    测试数据 #7: Accepted, time = 328 ms, mem = 948 KiB, score = 10

    测试数据 #8: Accepted, time = 343 ms, mem = 952 KiB, score = 10

    测试数据 #9: Accepted, time = 328 ms, mem = 948 KiB, score = 10

    Accepted, time = 2035 ms, mem = 952 KiB, score = 100

    代码

    #include<iostream>
    #include<cmath>
    using namespace std;
    int a[100000];
    long long ans=0;
    int main()
    {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++)
    {
    if(a[i]>a[i-1] && a[i]>a[i+1])
    {
    ans+=a[i]-max(a[i-1],a[i+1]);
    a[i]=max(a[i-1],a[i+1]);
    }
    if(a[i]<a[i-1] && a[i]<a[i+1])
    {
    ans+=min(a[i-1],a[i+1])-a[i];
    a[i]=min(a[i-1],a[i+1]);
    }
    ans+=abs(a[i-1]-a[i]);
    }
    cout<<ans;
    return 0;
    }

    vijos复活后第一题

  • 0
    @ 2013-07-15 13:37:15

    var
    n,i,p,q:longint;
    a:array[0..100001] of longint;
    ans:qword;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a)
    else exit(b);
    end;
    function min(a,b:longint):longint;
    begin
    if a>b then exit(b)
    else exit(a);
    end;
    begin
    readln(n);
    for i:=1 to n do
    read(a[i]);
    for i:=2 to n do
    begin
    p:=a[i-1] ; q:=a[i+1];
    if ((p>a[i]) and (a[i]>q)) or ((p<a[i]) and (a[i]<q)) then begin ans:=ans+abs(a[i]-p); continue end;
    if (a[i]<=p) and (a[i]<=q) then begin ans:=ans+min(p,q)-a[i]; a[i]:=min(p,q); ans:=ans+abs(a[i]-p); continue end;
    if (a[i]>=p) and (a[i]>=q) then begin ans:=ans+a[i]-max(p,q); a[i]:=max(p,q); ans:=ans+abs(a[i]-p); continue end;
    end;
    writeln(ans);
    end.

  • 0
    @ 2012-07-29 15:18:43

    不知道怎么证明,稀里糊涂就过了。

  • 0
    @ 2010-04-15 11:29:49

    "显然对于所有情况,都有如果a[i]修改过,那么a就不会再改或者改成和a[i]一样的数值," 这对吗。。楼下好多大牛都这样说啊

    反例

    105 100 110 108

  • 0
    @ 2009-11-09 08:36:04

    由传递性简单易证,当a[i]为valley或peak时变为周围的min或max最优。。

  • 0
    @ 2009-10-22 21:06:11

    ├ 测试数据 01:运行超时|无输出...

    ├ 测试数据 02:运行超时|无输出...

    ├ 测试数据 03:运行超时|无输出...

    ├ 测试数据 04:运行超时|无输出...

    ├ 测试数据 05:运行超时|无输出...

    ├ 测试数据 06:运行超时|无输出...

    ├ 测试数据 07:运行超时|无输出...

    ├ 测试数据 08:运行超时|无输出...

    ├ 测试数据 09:运行超时|无输出...

    ├ 测试数据 10:运行超时|无输出...

  • 0
    @ 2009-10-09 08:55:28

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

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

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

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

    ├ 测试数据 05:运行超时|无输出...

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

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

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

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

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

    为什么!!~- -

  • 0
    @ 2009-10-07 15:32:01

    乱搞秒杀………………

  • 0
    @ 2009-10-04 09:54:25

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    哈哈哈哈

  • 0
    @ 2009-10-02 20:36:04

    如何证明贪心可以得到最优解?

  • 0
    @ 2009-09-23 21:41:31

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var i,n:longint;

    a:array[0..100005]of longint;

    x:int64;

    function max(x,y:longint):longint;

    begin

    if x>y then max:=x else max:=y;

    end;

    function min(x,y:longint):longint;

    begin

    if xa)and(a[i]>a) then

    begin

    x:=x+abs(a[i]-max(a,a));

    a[i]:=max(a,a);

    end;

    if (a[i]

  • 0
    @ 2009-09-06 14:42:06

    这题也可以快排,再算sum=sum+abs(a[i]-a)(1

  • 0
    @ 2009-09-04 11:10:15

    假设存在 a[i]

    a[i]是低谷(a[i]a)。

    这样就把a[i]调节成与它最接近的旁边两个之中的一个数。

    !!这样确定了局部从a经过a[i]走到a不会走重复的高度了!!

    显然对于所有情况,都有如果a[i]修改过,那么a就不会再改或者改成和a[i]一样的数值,据此必然有无论a如何变化从a[i] 到a的路程总值都不变。

    从这里在把a当成a[i]处理,这样每次每次处理出来的都是局部最优最优的解。根据a[i] 到a的路程总值都不变就从局部推广到了整体,因此只要不断重复处理,最终结果必然是最优!

  • 0
    @ 2009-08-21 17:44:00

    证法1:对于a,b,c,d 当b在[a,c]中,最优;

    对于b,c,d 使c在中,最优;并且使c在中的同时不违反b在[a,c]中,所以全局最优

    证法2:对于一个序列满足任意a[i]在【a,a】之间 必有c在中,如果使c在外,必然更劣,所以这样最优,所以生成这样的序列

    这样证对吗?

  • 0
    @ 2009-08-21 10:01:39

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var i,n:longint;

    a:array[0..100005]of longint;

    x:int64;

    function max(x,y:longint):longint;

    begin

    if x>y then max:=x else max:=y;

    end;

    function min(x,y:longint):longint;

    begin

    if xa)and(a[i]>a) then

    begin

    x:=x+abs(a[i]-max(a,a));

    a[i]:=max(a,a);

    end;

    if (a[i]

  • 0
    @ 2009-08-19 09:46:18

    f表第i个调整为高度j的最优值。k枚举第i-1个的高度。

    F=Min{F+(H[i]-J)+|j-k|}

    o(n^3),dp它干嘛?

    但这位同学问dp算法的这种精神还是值得学习的。

    因为如果把调整第m个的高度和从m走到m+1的代价都改变一下,不是系数为1这样的代价的话,贪心显然就不可以了。

    我做过的原题是(姜碧野出的,为避嫌说明一下),

    从m走到m+1的代价=c*高度差,调整第m个的高度的代价是(j-h[m])^2。对于这道题来讲,只能用dp了。

    F=Min{F+(Hi-J)^2+C*|j-k|}

    对此方程的优化我就先不写了。

  • 0
    @ 2009-08-18 23:47:28

    abs.....忘了写....

信息

ID
1615
难度
5
分类
贪心 点击显示
标签
递交数
1950
已通过
746
通过率
38%
被复制
1
上传者