codeforces 505C C. Mr. Kitayuta, the Treasure Hunter (dp)-白红宇

codeforces 505C C. Mr. Kitayuta, the Treasure Hunter (dp)

阅读量：3711 次

发布时间：2019-05-21

本文共 1066 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

给出30000个岛，有n个宝石分布在上面，第一步到d位置，每次走的距离与上一步的差距不大于1，问走完一路最多捡到多少块宝石。

题目分析：

首先容易想到最暴力的方法：

定义状态dp[i][j]代表到达i位置上一步的大小是j的情况下最多捡到的宝石数。

按照题意模拟即可

但是这样在时间和空间上都是不被允许的

机智的人会发现，因为只有30000个点，所以步幅的变化范围上下不会超过250。

那么暴力搞就好了，我的挫代码就不上了，网上找到了一个黑科技的代码，相当简洁…..

AC代码（非本人代码）

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=100000000;const int INF=0x3f3f3f3f;const double eqs=1e-8;int dp[31000][300], w[31000], max1, max2;int dfs(int cur, int lenth){ if(cur>max1) return 0; if(dp[cur][lenth]!=-1) return dp[cur][lenth]; if(lenth>1) dp[cur][lenth]=max(dp[cur][lenth],dfs(cur+lenth-1,lenth-1)+w[cur]); dp[cur][lenth]=max(dp[cur][lenth],dfs(cur+lenth,lenth)+w[cur]); dp[cur][lenth]=max(dp[cur][lenth],dfs(cur+lenth+1,lenth+1)+w[cur]); max2=max(max2,dp[cur][lenth]); return dp[cur][lenth];}int main(){ int n, d, i, j, x, len, pre; max1=-1; scanf("%d%d",&n,&d); memset(w,0,sizeof(w)); memset(dp,-1,sizeof(dp)); for(i=0; i