题意：一些团队因为任务要去避难所，并且每个避难所必须要有团队在，避难所的数量小于等于团队的数量，
团队去避难所的消耗油量与路程成正比，求解最小耗油量。题目来源：2010 Northeastern European Regional Contest
输入：
T（示例）
n（团队个数）
a，b，c...（团队坐标，无序排列）
m（避难所个数）
a1，b1，c1...（避难所坐标，无序排列）
输出：
sum（总耗油量）
x，y，z...（团队按升序排序所到避难所序号值，注意不是坐标值）
思路：
一道超级考验理解英语智商的题目，反正光读懂题目意思，花了半个多小时，然后理解测试数据又花了半个多小时，题目整体看上去应该是用贪心+DP，先把给出的团队，避难所坐标排好序，然后找关于团队的状态转移方程，我解释下怎么理解这个状态转移方程，因为排好序后，随机选取一个下标为i的团队以及下标为j的避难所，那么要求i个团队到j个避难所所花费的总耗油量DP[i][j]，第i个团队根据最优原则，必然是去第j个避难所，那么前i-1个团队就有两种可能了，一种是去j-1个避难所，那么DP[i][j]=DP[i-1][j-1]+L[i][j]，第二种就是去j个避难所，因为这也是一种情况，那么此时DP[i][j]=DP[i-1][j]+L[i][j]，所以在这两种情况里面选出最优解即可，因为题目限制了内存，所以用滚动数组记录，最后打印团队到避难所相应下标需要按升序排列，注意下即可，关于滚动数组，其实只是一定程度减少了前面空间的浪费，与时间无关，也就是覆盖了之前的记录，类似于斐波那契数列的优化，我的理解是这样的，这里贴
一位大牛的blog讲解 我是链接，另外这道题的代码参考我是链接
毕竟太弱，写不出来
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long Max=(1LL)<<60;
short path[4010][4010];
long long f[4010];
struct N
{
long long dist;
int index;
int Find;
} team[4010],shelter[4010];
int n,m;
bool cmp(N a,N b)
{
return a.dist<b.dist;
}
bool cmp1(N a,N b)
{
return a.index<b.index;
}
void find_index(int i,int j)
{
if(i!=1) find_index(i-1,path[i][j]);
team[i].Find=shelter[j].index;
}
int main()
{
int T;
scanf("%d",&T);
for(int z=1; z<=T; z++)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%I64d",&team[i].dist);
team[i].index=i;
}
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
scanf("%I64d",&shelter[i].dist);
shelter[i].index=i;
}
sort(team+1,team+1+n,cmp);
sort(shelter+1,shelter+1+m,cmp); for(int i=0; i<=n; i++)
f[i]=Max;
f[1]=abs(team[1].dist-shelter[1].dist);
for(int i=2; i<=n; i++)
for(int j=min(i,m); j>=1; j--)
{
if(f[j]<f[j-1])
{
f[j]=f[j]+abs(team[i].dist-shelter[j].dist);
path[i][j]=j;
}
else
{
f[j]=f[j-1]+abs(team[i].dist-shelter[j].dist);
path[i][j]=j-1;
}
}
printf("%I64d\n",f[m]);
find_index(n,m);
sort(team+1,team+1+n,cmp1);
for(int i=1; i<=n-1; i++)
printf("%d ",team[i].Find);
printf("%d\n",team[n].Find);
}
return 0;
}