老鼠和洞按坐标排序
f[i][j]表示前i个洞进j只老鼠的最短距离
比赛的时候强行分三类去推式子，推是推出来了，也看出来是可以用三个单调队列去优化的，但是太繁琐了，要我敲我真没办法T^T
赛后经 onion_cyc 点拨才知道可以对每一个洞分别处理出到每只老鼠的距离...
f[i][j]=f[i-1][k]+sum[j]-sum[k](j-k<=v[i])
然后这个显然是可以单调队列优化的，效率O(NM)
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=5010,inf=1e9; struct poi{int x,v;}hole[maxn]; int n,m,x,y,z,tot; ll f[maxn][maxn],sum[maxn]; int ms[maxn],q[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } bool cmp(poi a,poi b){return a.x<b.x;} int main() { read(m);read(n); for(int i=1;i<=m;i++)read(ms[i]); for(int i=1;i<=n;i++)read(hole[i].x),read(hole[i].v); sort(ms+1,ms+1+m);sort(hole+1,hole+1+n,cmp); f[0][0]=0;for(int i=1;i<=m;i++)f[0][i]=1ll*inf*10000; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) sum[j]=abs(hole[i].x-ms[j]),sum[j]+=sum[j-1]; int l=1,r=1;q[1]=0; for(int j=1;j<=m;j++) { while(l<=r&&j-q[l]>hole[i].v)l++; while(l<=r&&f[i-1][j]-sum[j]<f[i-1][q[r]]-sum[q[r]])r--; q[++r]=j; f[i][j]=f[i-1][q[l]]+sum[j]-sum[q[l]]; } } printf("%lld ",f[n][m]==1ll*inf*10000?-1:f[n][m]); return 0; }