求救第九个点!!!

求救第九个点!!!

还是不知道任何处理这个点,错的和前面各位仁兄所说的一样

2 条评论

  • @ 2020-03-23 15:40:47
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    #define inf 0x3fffffff
    using namespace std;
    int w,p,h,n,t,r,v,s,ans2=0,ans=0,T,f[3005][3005],g[3005][3005];
    int main(){
        cin>>w>>p>>h>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>t>>r>>v>>s;
            if(h%v==0)t+=h/v;
            else
            {
                ans2+=s;
                continue;
            }
            T=max(T,t);
            g[t][r]=s;
            if(abs(p-r)>t)
              ans2+=s;
        }
        for(int i=0;i<=T;i++)
          for(int j=0;j<=w+1;j++)
            f[i][j]=-inf;
        f[0][p]=0;
        for(int i=1;i<=T;i++)
          for(int j=1;j<=w;j++)
            {
                if(f[i-1][j]!=-inf)f[i][j]=f[i-1][j]+g[i][j];
                if(f[i-1][j-1]!=-inf)f[i][j]=max(f[i][j],f[i-1][j-1]+g[i][j]);
                if(f[i-1][j+1]!=-inf)f[i][j]=max(f[i][j],f[i-1][j+1]+g[i][j]);
                ans=max(ans,f[i][j]);
            }
        cout<<ans<<"\n"<<ans2;
        return 0;
    }
    
  • @ 2020-03-23 15:40:10

    这道题目显然是一个dp,而且方程也很好想。
    f[i][j]表示在i时刻和j位置所取到的最大值,那么我们可以得到方程为f[i][j]=max(f[i-1][j],f[i-1][j-1],f[i-1][j+1])+w[i][j];
    其中w[i][j]表示i时刻j位置可以接到的价值。
    那么我们只要预处理出w[i][j]就可以了。
    但是有一些细节是需要注意的,比如说:
    - 当礼物在某一秒末 恰好 到达小杉所在的格子中,小杉才能接到这个礼物。 注意恰好。不在某一秒末的我们肯定是拿不到的
    - 还有拿不到的就是在一开始我们直接前往也无法拿到的。
    - 另外需要注意的是,某个礼物的价值可能是负的,那么f数组一定要赋-inf,否则要出事

  • 1

信息

ID
1235
难度
7
分类
动态规划 点击显示
标签
递交数
1194
已通过
227
通过率
19%
被复制
1
上传者