/ Vijos / 题库 / 天堂的馈赠 /

题解

49 条题解

  • 2
    @ 6 年前 
    //比较简单的一道dp
//先预处理出每一秒落在某处的礼物价值是多少，然后开始dp，dp[i][j]表示
//在i时刻位于j坐标时的最大价值
//不能拿到的礼物有两种情况：一是下落时间不为整数（砸稀烂了），二是
//从一开始就跑也拿不到
//需要注意的是天使扔完礼物后空中可能还有正在下落的礼物，所以t要开大
//一点
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int yu[3010][510],dp[3010][510];
int main()
{
    memset(dp,-0x3f,sizeof(dp));
    int w,p,h,n,i,j,t,r,v,s,now,ans=0,bu=0;
    cin>>w>>p>>h>>n;
    for(i=1;i<=n;i++)
     {
        cin>>t>>r>>v>>s;
        if(h%v==0)
         now=h/v;
        else
         {
          bu+=s;
          continue;
         }
        yu[t+now][r]+=s;
        if(t+now<abs(p-r))
         bu+=s;
     }
    dp[0][p]=0;
    for(i=1;i<=2000;i++)
     for(j=1;j<=w;j++)
      {
        dp[i][j]=max(dp[i-1][j],max(dp[i-1][j-1],dp[i-1][j+1]));
        dp[i][j]+=yu[i][j];
        ans=max(ans,dp[i][j]);
      }
    cout<<ans<<endl<<bu;
}
    Copy
  • 1
    @ 15 年前

    这个题动态规划方程非常简单，关键是细节。

    细节注意：

    1.首先解释一下题意。第二问问的是永远不能接到的，这包括落地时间不是整数的，以及在规定时间内到不了的，但是不包括在坐标轴外的！！也就是说，如果第0号位置有东西，而且规定时间能到，就不算接不到。这显然与题意不服，但是数据就是这么设计的，这也就不难解释第九个点为什么大部分人都挂掉了。

    2.数组要够大，1500不够，算上落地时间，应该有2000。

    3.这个题第一次交就过了，那可真的就是天堂的馈赠了……

  • 0
    @ 8 年前 
    #include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int f[2050][501],val[2050][501];
int main()
{
    int w,p,h,n,ans1=0,ans2=0,maxt=0;
    cin>>w>>p>>h>>n;
    for(int i=1;i<=n;i++)
    {
        int t,r,v,s;
        cin>>t>>r>>v>>s;
        if(h%v==0&&abs(p-r)<=t+h/v/*落地所需时间大于到达r所需时间*/)
        {
            val[t+h/v][r]+=s;
            maxt=max(maxt,t+h/v);
        }//如果落地时间不是整数，或者已经落地了却到不到r则接不到礼物 
        else ans2+=s;
    }
    memset(f,128,sizeof f);
    f[0][p]=0;
    for(int i=1;i<=maxt;i++)
        for(int j=1;j<=w;j++)
            f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+val[i][j];
    for(int i=1;i<=w;i++)
        ans1=max(ans1,f[maxt][i]);
    printf("%d\n%d",ans1,ans2);
}```
水一发
    Copy
  • 0
    @ 9 年前

    先对礼物的时间从小到大进行排序
    dp[t][r]：=第t秒在r处获得的最大的价值。
    先由dp[t-1][] 更新dp[t]
    然后如果有礼物刚好是t秒，进行状态转移
    dp[t][r]=max(dp[t-1][r],max(dp[t-1][r-1],dp[t-1][r-1]))+val 这里一定要取某个礼物。所以不能和当前dp[t][r]比较

  • 0
    @ 15 年前

    编译通过...├ 测试数据 01：答案正确...ms├ 测试数据 02：答案正确...ms├ 测试数据 03：答案正确...ms├ 测试数据 04：答案正确...25ms├ 测试数据 05：答案正确...ms├ 测试数据 06：答案正确...ms├ 测试数据 07：答案正确...56ms├ 测试数据 08：答案正确...ms├ 测试数据 09：答案正确...ms├ 测试数据 10：答案正确...25msAccepted 有效得分：100 有效耗时：106ms

  • 0
    @ 15 年前

    f表示第i秒人在第j格能获得的最大价值

    a表示第i秒第j个格子的礼物的总价值

    显然，

    f:=MAX(f,f,f)+a

    Ans:=MAX(f)

    P.S.循环时1

  • 0
    @ 15 年前

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    把j-1y? x:y;

    }

    long Abs(long x)

    {

    return x>=0? x:(-x);

    }

    int main()

    {

    scanf("%ld%ld%ld%ld",&w,&p,&h,&n);

    long i,j;

    for(i=1;i

  • 0
    @ 15 年前

    其实这题并不难...

    一开始想复杂了...其实暴力一点也是0ms...

    但是我做了些优化（时间估计有误），由于水平问题，反而一交，一WA...

    我是用t[i]第i个点的下落时间表示时间的.可惜水平有限...

    其实直接for i:=1 to 2000 do 就行了...囧...

    最后将代码减少了1/3，AC了...这题囧囧的...

  • 0
    @ 15 年前

    呃。。类 数字三角形。

  • 0
    @ 15 年前

    for (int i = 1; i

  • 0
    @ 15 年前

    whyvine的解题报告：

    http://blog.sina.com.cn/s/blog_618b6ea70100eibv.html

  • 0
    @ 15 年前

    编译通过...

    ├ 测试数据 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
    @ 15 年前

    搞了半天原来是第二问少考虑了一种情况。

    (h mod v 0) 或 (t+(h div v)

  • 0
    @ 15 年前

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    恨...一开始判断不能接多写了个+t导致+了两个t

    竟然还过了4个点

    郁闷 交了6次

  • 0
    @ 15 年前

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    就因为一个数据范围，害得我3次存取非法

  • 0
    @ 15 年前

    忘加F[0,P]:=0;

    竟然还有70分

  • 0
    @ 15 年前

    其实接不到的情况就两个：

    1.时间不是整数

    2.与p的距离大于掉地的时间

  • 0
    @ 15 年前

    果然巨恶。。。。

    万恶的第9个点。。。

  • 0
    @ 16 年前

    第9个数据到底是怎么回事?

  • 0
    @ 16 年前

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    `3各地方\``少写了3个字母·····

    检查了将近一个小时···········

    ·········

天堂的馈赠

信息

ID
1235
难度
7
分类
动态规划 点击显示
标签
递交数
1259
已通过
244
通过率
19%
被复制
6
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1