CodeForces - 797F Mice and Hole

题意：有n只老鼠，m个洞。n只老鼠的坐标分别为x[i]，m个洞坐标分别为p[i]，能装c[i]只老鼠。现在老鼠要往洞里跑，求所有老鼠跑的最短路线之和。

解：一开始准备拿老鼠转移，然后复杂度爆了，于是进行一些观察。先本能地给洞和老鼠排个序，然后发现跑的路最短的情况下，一个洞里的老鼠肯定是连续的。嗯怎么有点像我出的那个题。考虑设dp[i][j]为前i个洞里装了前j只老鼠，先不管能不能装下，那么转移的时候就是枚举新出现的洞里装几只老鼠，转移方程为：

dp[i][j]=min(dp[i-1][k]+sum[k+1...j])，其中[k+1...j]要小于等于洞的容量。

这样是O(n²m)的。因为每次转移都是取连续的一段区间，可以用单调队列优化一下。注意把不可行的方案设为inf。

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxx 1005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 2520
ll x[5005];
vector<pair<ll,ll> > v;
ll dp[5005][5005]={0};
ll sum[5005]={0};
int q[5005]={0};
signed main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&x[i]);
    }
    ll res=0;
    for(int i=1;i<=m;i++){
        ll p,c;
        scanf("%lld%lld",&p,&c);
        v.push_back(make_pair(p,c));
        res+=c;
    }
    if(res<n){
        printf("-1\n");
        return 0;
    }
    sort(x+1,x+n+1);
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++){
        dp[0][i]=1e18;
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            sum[j]=sum[j-1]+abs(v[i-1].first-x[j]);
        }
        int head=1,tail=0;
        for(int j=0;j<=n;j++){
            while(head<=tail&&q[head]<j-v[i-1].second) head++;
            while(head<=tail&&dp[i-1][q[tail]]-sum[q[tail]]>=dp[i-1][j]-sum[j]) tail--;
            q[++tail]=j;
            dp[i][j]=dp[i-1][q[head]]+sum[j]-sum[q[head]];
        }
    }
    printf("%lld\n",dp[m][n]);
    return 0;
}