505C Mr. Kitayuta, the Treasure Hunter-白红宇

505C Mr. Kitayuta, the Treasure Hunter

阅读量：7210 次

发布时间：2019-06-29

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

题目大意

一共有30000个位置，从第0个位置开始走，第一次走k步，对于每一次走步，可以走上一次的k_i+1 ，k_i ，k_i-1步数（必须大于等于1），每个岛上有value，求最大能得到的value能有多少。

分析

首先我们不难想到dpij表示走到第i个位置，上次走的步数为j，然而30000*30000时间复杂度和空间复杂度都会爆炸，所以我们考虑如何优化掉一维，然而我们发现是无法优化掉一维的。

但由于一个只有30000个位置，所有我们想到上次走的步数的所有可能情况可能不是很多，由式子d+(d+1)+(d+2)+…+(d+maxl)≤30000可得maxl大致是250，也就是说上次走的步数最少是d-250，最多是d+250.于是我们得到dpij，其中i表示考虑到第i个位置，j表示上次走的长度-d，注意为了防止数组出现负数我们将第二维统一加上maxl。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define sp cout<<"---------------------------------------------------"<
                   
                    0) dp[i+j+d][j+maxl]=max(dp[i+j+d][j+maxl],dp[i][j+maxl]+cnt[i+j+d]); if(j+d-1>0&&i+j+d-1<=N&&j-1>=-maxl) dp[i+j+d-1][j-1+maxl]=max(dp[i+j+d-1][j-1+maxl],dp[i][j+maxl]+cnt[i+j+d-1]); if(j+d+1>0&&i+j+d+1<=N&&j+1<=maxl) dp[i+j+d+1][j+1+maxl]=max(dp[i+j+d+1][j+1+maxl],dp[i][j+maxl]+cnt[i+j+d+1]); } int ans=0; for(i=0;i<=N;i++)for(j=-maxl;j<=maxl;j++)ans=max(ans,dp[i][j+maxl]); cout<
                    
                     <

转载于:https://www.cnblogs.com/yzxverygood/p/9292707.html

你可能感兴趣的文章

1.1.3 Getting Started_Budding Your First App_Building a Simple User Interface