//比较简单的一道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;
}

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

细节注意：

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

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

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

#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);
}```
水一发

先对礼物的时间从小到大进行排序
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]比较

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

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

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

显然，

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

Ans:=MAX(f)

P.S.循环时1

编译通过...

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

其实这题并不难...

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

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

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

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

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

呃。。类 数字三角形。

for (int i = 1; i

whyvine的解题报告：

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

dp秒杀

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

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

编译通过...

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

竟然还有70分

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

1.时间不是整数

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

果然巨恶。。。。

万恶的第9个点。。。

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

编译通过...

├ 测试数据 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个字母·····

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

·········