题意： 在连续的 n 秒中，每秒会出现 m 个龙珠，出现之后会立即消失，知道了第一秒所在的位置，每从一个位置移动到另一个位置的时候，消耗的价值为 abs(i-j), 知道了次出现的龙珠的价值，问 n 秒之后得到的最大价值是多少。

思路：这道题朴素的做法时间复杂度为O(n*n*m)勉强可以水过去，正解应该是用单调队列的思路维护最小值优化。

由状态转移方程dp[i][j] = min{ dp[i-1][k] + abs(pos[i-1][k]-pos[i][j]) } + cost[i][j]

可以推出dp[i][j]+pos[i][j]+cost[i][j] = min(dp[i-1][k]+pos[i-1][k]) (当pos[i-1][k]>pos[i][j]))

所以可以按位置排序后维护dp[i-1][k]+pos[i-1][k])的最小值。

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
        
       
      
     
    
   
  

?

?