uva

数轴上有 nn 个施工队 a[1…n]，m 个受损的防御位点 b[1…m]，

每个施工队都要进入一个防御位点，而且每个防御位点都要有人进入，问施工队最少需要移动多少距离。

先排序

队伍i，防御点j

 f[i][j] =min( f[i-1][j] ,f[i-1][j-1] ) +dis(i,j)

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std ;
 const int N=4005;
 
 #define int long long
 
  const int inf=1e18;
 struct T{
     int id,v;
 };
 int cmp(T a,T b){
     return a.v<b.v;
 }
 T a[N],b[N];
 int f[N][N],n,m;
 int r[N][N],ans[N];
  
 void print(int x,int y){
     if(x==0&&y==0) return;
     
     ans[a[x].id]=b[y].id;
     if(r[x][y]) print(x-1,y-1); else print(x-1,y);
 }
 signed main(){
     //freopen("in","r",stdin);
     while(cin>>n){
     int i,j;
     for(i=1;i<=n;i++) cin>>a[i].v,a[i].id=i;
     cin>>m;
     for(i=1;i<=m;i++) cin>>b[i].v,b[i].id=i;
     sort(a+1,a+1+n,cmp);
     sort(b+1,b+1+m,cmp);
     
     for(j=1;j<=m;j++) f[0][j]=inf;  
    f[0][0]=0;
     
     for(i=1;i<=n;i++){
     for(j=0;j<=m;j++) f[i][j]=inf; 
      
      for(j=1;j<=min(i,m);j++){
          int t=abs(a[i].v-b[j].v);
          if(f[i-1][j-1]<=f[i-1][j]){
              f[i][j]=f[i-1][j-1]+t;
              r[i][j]=1;
          }
          else{
              f[i][j]=f[i-1][j]+t;
              r[i][j]=0;
          }
      }
    }
    cout<<f[n][m]<<endl;
    print(n,m);
    for(i=1;i<n;i++) cout<<ans[i]<<' ';
    cout<<ans[n];
    cout<<endl;
    }
    
 }