首页 > 代码库 > LA 4987 背包
LA 4987 背包
题意：
有n个施工队，给定他们的位置，有m个防空洞，给定位置，求将施工队放到m个防空洞里面，最少的总距离？
n<=4000
分析：
dp[i][j] 前 i 个施工队，放到前 j 个防空洞里面的最少距离；
dp(i+1,j) = min(dp(i,j),dp(i,j-1)) + dist(a[i] - b[j])；
DP采用滚动数组；
那么，第二维的防空洞该怎么循环呢？
因为，每个防空洞都要有，那么这类似于背包中的容量，刷表的方式；
#include <bits/stdc++.h>using namespace std;const int maxn = 4000+5;const int inf = 0x3f3f3f3f;struct node { int d; int id; int ans;}A[maxn],B[maxn];long long dp[maxn];int path[maxn][maxn];int n,m;bool cmp(node a,node b) { if(a.d==b.d) return a.id < b.id; return a.d < b.d;}void find_path(int i,int j) { if(i) find_path(i-1,path[i][j]); A[i].ans = B[j].id;}int cmp1(node a,node b) { return a.id < b.id;}int main(){ while(~scanf("%d",&n)) { for(int i=0;i<n;i++) { scanf("%d",&A[i].d); A[i].id = i; } scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%d",&B[i].d); B[i].id = i; } sort(A,A+n,cmp); sort(B,B+m,cmp); memset(dp,inf,sizeof(dp)); dp[0] = abs(A[0].d-B[0].d); for(int i=1;i<n;i++) { for(int j=min(m-1,i);j>=0;j--) { if(!j||dp[j]<dp[j-1]) { path[i][j] = j; dp[j] = dp[j] + abs(A[i].d-B[j].d); } else { path[i][j] = j-1; dp[j] = dp[j-1] + abs(A[i].d - B[j].d); } } } printf("%lld\n",dp[m-1]); find_path(n-1,m-1); sort(A,A+n,cmp1); for(int i=0;i<n;i++) printf("%d ",A[i].ans+1); puts(""); } return 0;}
LA 4987 背包
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。