目录
codeforces 797F Mice and Holes题意题解Code
codeforces 797F Mice and Holes
题目传送门1
题意
有\(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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>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<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>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<rhs.p;
}
}h[N];
/*==================Define Area================*/
int main() {
read(n);read(m);
for(int i=1;i<=n;i++) {
read(x[i]);
}
for(int i=1;i<=m;i++) {
read(h[i].p);read(h[i].c);
tot+=h[i].c;
}
if(tot<n) return puts("-1"),0;
sort(x+1,x+1+n);sort(h+1,h+1+m);
for(int i=1;i<=n;i++) f[0][i]=inf;
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
sum[j]=sum[j-1]+(ll)abs(h[i].p-x[j]);
}
int l=1,r=0;
for(int j=0;j<=n;j++) {
while(l<=r&&que[l]<j-h[i].c) ++l;
while(l<=r&&f[i-1][j]-sum[j]<=f[i-1][que[r]]-sum[que[r]]) --r;
que[++r]=j;
int t=que[l];
f[i][j]=f[i-1][t]+sum[j]-sum[t];
}
}
printf("%lld\n",f[m][n]);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9573239.html
相关资源：JAVA上百实例源码以及开源项目
