目录

codeforces 797F Mice and Holes

题意

有\(n\)个老鼠，每个老鼠原来在\(xi\)的位置上，有\(m\)个洞，每个洞分别在\(pi\)的位置上，一共可以容纳\(ci\)只老鼠，问所有的老鼠都跑进洞里，最小的跑动距离总和是多少。如果无解，则输出-1。\((1 \leq n,m,cj \leq 5000,-10^9 \leq xi,pi \leq 10^9)\)

题解

我们先把老鼠和洞按照坐标排序一下，然后我们可以简单地发现钻进一个洞里的老鼠一定都是连续的一段，于是我们记\(f[i][j]\)表示前\(i\)个洞钻进了\(j\)只老鼠的最短距离。这样我们可以记一个老鼠跑动距离的前缀和，就可以进行\(O(n^2m)\)的转移了。然后我们考虑如何优化这个\(Dp\)，实际上通过证明可以发现这个\(Dp\)实际上是单调的，然后我们就可以用单调队列进行维护，类似于斜率优化一样进行\(Dp\)即可。不过需要注意的是\(f[i][j]\)同样可以转移到\(f[i+1][j]\)，所以我们需要先维护玩这个单调队列，并把当前枚举到的\(j\)加入单调队列之后再进行\(Dp\)转移，不然会少掉一种情况。

Code

#include 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}template
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}/*================Header Template==============*/#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);const int N=5005;const ll inf=0x7fffffffffff;int n,m,tot;ll f[N][N],sum[N];int x[N],que[N];struct hole {    int p,c;    bool operator < (const hole &rhs) const {        return p