学步园

首先，说以下本题目的状态转移方程为：

以d[ i ][ j ] = max ( d[ k ][ j +1 ] + sumc（i+1-->k  , j+1） 其中sumc（i+1-->k  , j+1）代表从i+1到k都到j+1避难 ) ；

首先说明为什么一定是连续 11...22..33...44..5..6 连续的取值；

所有 的 n支队伍和m个避难所要先排序；

我们可以假设最优解中除了必须的从n中取出的m个依次 对应 1 ,2, 3, 4,5,6,7直到m则这m只队伍一定是升序的，可贪心证明；

然后剩下的n-m支队伍会和在一起构成11...22..33...44..55..66..因为16...22..33...44..55..16. 任意两个位置错位则交换过来的解不会更差；

#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include <cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

const LL inf = 1e14;
const int maxn = 4010;
struct node{
  long long x,p,res;
  node(int x=0,int p=0):x(x),p(p){}
  bool operator < (const node& rhs)const{
    return  x<rhs.x;
  }
};
LL d[maxn][maxn],n,m,res[maxn];
node a[maxn],b[maxn];
bool vis[maxn][maxn];
LL dp(int i,int j){
    if(vis[i][j]) return d[i][j];
    vis[i][j] = true;
    if(i==n){
         if(j<m) return d[i][j]=inf;
         return d[i][j] = 0;
    }
    d[i][j] = inf;
    if(j<m)
    d[i][j]=dp(i+1,j+1)+abs(a[i+1].x-b[j+1].x);
    if(n-(i+1)>=m-j)
        d[i][j]=min(d[i][j],dp(i+1,j)+abs(a[i+1].x-b[j].x));
    return d[i][j];
}
void print_ans(int i,int j){
   if(i==n) return ;
   if(d[i][j]==dp(i+1,j+1)+abs(a[i+1].x-b[j+1].x)){
      res[a[i+1].p] = b[j+1].p;
      print_ans(i+1,j+1);
   }
   else {
      res[a[i+1].p] = b[j].p;
      print_ans(i+1,j);
   }
}
int main()
{
    while(scanf("%lld",&n)==1){
       for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].x);
        a[i].p=i;
       }
       scanf("%lld",&m);
       for(int i=1;i<=m;i++){
        scanf("%lld",&b[i].x);
        b[i].p = i;
       }
       sort(a+1,a+n+1);
       sort(b+1,b+m+1);
       for(int i=0;i<=n;i++)
          for(int j=0;j<=m;j++)
              vis[i][j] =false;
        printf("%lld\n",dp(1,1)+abs(a[1].x-b[1].x));
        res[a[1].p]=b[1].p;
        print_ans(1,1);
        for(int i=1;i<=n;i++){
             if(i>1) printf(" ");
             printf("%d",res[i]);
        }
        printf("\n");
    }
    return 0;
}