题解

46 条题解

  • 4
    @ 2017-09-16 14:57:59

    简单推了推,发现就是单调DP。

    说下思路吧,题中说我们只能获得 “一次能量球的值” ,但是我们的跳是可以跳多次的。解题的关键在于我们必须尽量减少 “跳跃时的代价” ,所以我们不会做出以下决策。

    1. 后次的跳跃高度比前次的还低或相等。
    2. 刚拿到能量就让自己跳到最高。(这是一种贪心策略,实际一般会错误)

    想到我们在达到我们的最大高度前想要尽可能的保留更多的能量,我们容易想到用dp实现。

    F[i] 表示吃到第i高的能量球时体力的最大值,易知转移。

    F[i] = F[j] + A[i]-A[j](A用于保存前缀和,表示这一次跳跃获得的能量)+ i * 100(跳跃的代价)(0<=j<=i)

    由以上转移方程可知,F[i]的负代价与j无关,而正代价随j的减少而增大(因为能量一定为正)
    ,于是用单调队列,保存能够跳跃到当前点的最小状态转移即可。

    #include <cstdio>
    #include <iostream>
    using namespace std;
    int N, M;
    int A[2000005], F[2000005];
    int Q[2000005], L, R;
    int main () {
        
        cin >> N >> M;
        A[0]=F[0]=M;
        for(int i=1; i<=N; i++) cin >> A[i], A[i]+=A[i-1];
        L=1, R=0, Q[R]=0;
        for(int i=1; i<=N; i++) {
            while(i*100>F[Q[R]]&&R<L) R++;  
            Q[L++]=i;
            F[i]=F[Q[R]]+(A[i]-A[Q[R]])-i*100;
        }
        cout << F[N];
        return 0; 
        
    }
    
    • @ 2020-08-04 10:51:07

      您的代码可真的清奇,R在左,L在右。

  • 1
    @ 2017-09-08 18:37:52

    #include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<queue>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int s[2000005],f[2000005],i,j,k,n,m,q[2000005],l,r;
    int main()
    {
    scanf("%d%d",&n,&f[0]);
    q[1]=0;l=1;r=1;
    for(i=1;i<=n;i++)
    {
    scanf("%d",&s[i]);
    s[i]+=s[i-1];
    }
    for(i=1;i<=n;i++)
    {
    while(l<=r&&f[q[l]]<i*100) l++;
    f[i]=f[q[l]]-s[q[l]]+s[i]-i*100;
    while(l<=r&&f[q[r]]-s[q[r]]<=f[i]-s[i]) r--;
    q[++r]=i;

    }
    printf("%d",f[n]);
    return 0;
    }

  • 1
    @ 2017-07-08 17:39:57

    #include<cstdio>
    using namespace std;
    #define N 2e6+5
    long long a[(int)N];
    long long dp[(int)N];
    using namespace std;
    long long nextInt() {
    long long x;
    char c;
    do c=getchar(); while (c<'0'||c>'9');
    x=c-'0';
    while ('0'<=(c=getchar())&&c<='9') x=x*10+c-'0';
    return x;

    }

    int main()
    {

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
    long long x=nextInt();
    a[i]=a[i-1]+x;
    }
    dp[0]=m;
    int i=0;
    for(int j=1;j<=n;j++)
    {
    while(dp[i]<j*100) i++;
    dp[j]=dp[i]+a[j]-a[i]-j*100;
    }

    printf("%lld\n",dp[n]);
    return 0;
    }

  • 1
    @ 2017-05-26 11:30:16

    单调队列优化Dp

    int main()
    {
        scanf("%d%d",&n,&f[0]);
        For(i,1,n)  scanf("%d",&p),sum[i]=sum[i-1]+p;
        l=1;r=1;q[1]=0;v[1]=f[0];
        For(i,1,n)
        {
            while(l<r&&f[q[l]]<i*100)   l++;
            f[i]=+sum[i]+v[l]-i*100;
            int tv=f[i]-sum[i];
            while(l<r&&tv>v[r]) r--;
            q[++r]=i;v[r]=tv;
        }
        printf("%d\n",f[n]);
    }
    
  • 0
    @ 2016-08-13 08:53:17
    //DP嘛;
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    #define LL long
    #define M 2000001
    LL n,m,i,x,h,l;
    LL f[M],s[M]={0},num[M];
    void init()
    {
        scanf("%d%d",&n,&m);
        for (i=1;i<=n;i++)
        {
            scanf("%d",&x);
            s[i]=s[i-1]+x;
        }
        return;
    }
    
    void dp()
    {
        h=1,l=0;
        num[h]=0;
        f[0]=m;
        for (i=1;i<=n;i++)
        {
            while (f[num[h]]<i*100 && h<=l)
                h++;
            f[i]=f[num[h]]+s[i]-s[num[h]]-i*100;
            if (f[i]>f[num[l]])
            {
                l++;
                num[l]=i;
            }
        }
        return;
    }
    int main()
    {
        init();
        dp();
        cout<<f[n]<<endl;
    }
    
  • 0
    @ 2016-03-18 20:13:16

    教主飞了……

  • 0
    @ 2013-08-07 21:02:21

    没有单调队列。,。,。。,用了个flag 也是n吧。,。,但是时间1600++不知道为什么??

  • 0
    @ 2010-04-15 19:09:17

    记录页面看到评测机是 Vijos Mini 70分

    点进去变成 Ed***|**,100分

    退回页面刷新,成了 100分

  • 0
    @ 2009-11-10 11:45:35

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    话说,数据类型很重要。。

    int64或者double就超时了,所以我严格限制每一个数的范围

    改用longint的就用long,改用word的就用word

  • 0
    @ 2009-11-09 08:01:11

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    一次AC,爽!可惜时间....囧~~~

    单调队列是个好东西啊!

    • @ 2015-11-18 20:20:22

      编译成功

      测试数据 #0: Accepted, time = 0 ms, mem = 23736 KiB, score = 10
      测试数据 #1: Accepted, time = 15 ms, mem = 23736 KiB, score = 10
      测试数据 #2: Accepted, time = 0 ms, mem = 23732 KiB, score = 10
      测试数据 #3: Accepted, time = 0 ms, mem = 23736 KiB, score = 10
      测试数据 #4: Accepted, time = 46 ms, mem = 23736 KiB, score = 10
      测试数据 #5: Accepted, time = 31 ms, mem = 23736 KiB, score = 10
      测试数据 #6: Accepted, time = 46 ms, mem = 23732 KiB, score = 10
      测试数据 #7: Accepted, time = 811 ms, mem = 23732 KiB, score = 10
      测试数据 #8: Accepted, time = 842 ms, mem = 23736 KiB, score = 10
      测试数据 #9: Accepted, time = 717 ms, mem = 23732 KiB, score = 10
      Accepted, time = 2508 ms, mem = 23736 KiB, score = 100
      ————————————————————————————
      那我的时间咋办???

  • 0
    @ 2009-11-04 23:08:56

    教主好能跳 要是有第一宇宙速度就好了 直接 去火星(时间好像有点久)深造

  • 0
    @ 2009-11-01 23:19:30

    不用单调队列的..

    f[i]:=max{f[j]+sum[i]-sum[j]-i*100=sum[i]-i*100-(sum[j]-f[j])=常数-(到达J的消耗)},f[j]>=i*100

    显然 对于J递增,到达J的消耗递增,因为高度增加..

    那么f[i]就是关于j的递减函数,这样就不需要用到队列,只要一个指针p指向满足f[j]>=i*100的最小的J就可以了.

    for i:=1 to n do begin

    while f[p]

  • 0
    @ 2009-11-01 18:31:58

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    sunny 好慢

  • 0
    @ 2009-10-30 11:16:26

    编译通过...

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

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

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

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

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

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

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

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

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

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

    弱弱的问一句.. 什么是单调队列??

    var i,j,k,l,m,n,oo,a:longint;

    f,sum:Array[0..2000000]of longint;

    begin

    readln(n,m);

    f[0]:=m;

    for i:=1 to n do

    begin

    read(a);

    sum[i]:=sum+a;

    for j:=oo to i-1 do

    if f[j]>=i*100 then

    begin

    oo:=j;

    f[i]:=f[j]+sum[i]-sum[j]-i*100;

    break;

    end;

    end;

    writeln(f[n]);

    end.

  • 0
    @ 2009-10-24 17:31:14

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    我让此题通过率增加一个百分点!

  • 0
    @ 2009-10-24 07:48:39

    单调队列.......

    就是可以删头然后加入尾的咯,

    保证要加入的元素大于队尾元素

  • 0
    @ 2009-10-20 14:25:12

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    sunny进步了,本来会超

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

    我们伟大的yz的LHX教主啊!!!

    OrzING!!!

  • 0
    @ 2009-09-24 16:21:20

    单调队列...

    折腾死我了。

  • 0
    @ 2009-09-15 09:44:05

    动态转移方程是

    f[i]=max(f[j]+sum[i]-s[j])-i*100

    考虑每一个在1..i-1的j

    如果f[j]=i*100,考虑到跳到同一个高度的获得的能量总和是一定的,那么消耗的能量越少,当前的能量越多。那么显然对于j1

信息

ID
1617
难度
6
分类
动态规划 | 单调性DP 点击显示
标签
递交数
1855
已通过
469
通过率
25%
被复制
2
上传者