题意：有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(n2m)的。因为每次转移都是取连续的一段区间，可以用单调队列优化一下。注意把不可行的方案设为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;
}

View Code

 

原文地址：http://www.cnblogs.com/capterlliar/p/16906352.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性