Mice and Holes 单调队列优化dp

n个老鼠，m个洞，告诉你他们的一维坐标和m个洞的容量限制，问最小总距离。1 ≤ n, m ≤ 5000。

​ 首先列出朴素的dp方程：\(f[i][j]=min(f[i-1][k]+s[j]-s[k])\)，其中\(f[i][j]\)表示前i个洞，有j个老鼠进洞。s[j]-s[k]表示第k+1到j个老鼠进洞的路径和。然后我们发现，\(f[i][j]\)的值取决于最小的\(f[i-1][k]-s[k]\ (k<=j)\)，同时，j-k必须小于等于第i个洞的容量。于是我们建一个单调队列，队列存储最优的k。然后如果\(j-q[head]\)大于第i个洞的容量，那么head++，然后如果\(f[i-1][j]\)大于队列末尾，那么就一直tail--。这样就可以把\(O(n^3)\)的时间复杂度优化成O(n^2)。

​ 对了，初始化的时候要注意，想清楚没有优化的时候是什么样的状态。其实不难的。

#include 
    
     #include 
     
      #include 
      
       typedef long long LL;const LL maxn=5005, INF=1e18;inline LL abs(LL x){ return x<0?-x:x; }struct Hole{    LL pos, cap;    void set(LL x, LL y){ pos=x; cap=y; }}hole[maxn];bool cmp(const Hole &a, const Hole &b){    return a.pos
       
        pre[i]) break;            //不能让这个洞容纳更多老鼠            while (head
        
         hole[i].cap) ++head;            //单调队列，不是min的通通吃掉            while (head
         
          <= fpre[queue[tail-1]]-s[queue[tail-1]]) --tail; queue[tail++]=j; fnow[j]=fpre[queue[head]]+s[j]-s[queue[head]]; } for (LL j=0; j<=n; ++j) fpre[j]=fnow[j]; } printf("%lld", fnow[n]);}