题目描述

给n个数，对于$a_i$数找出$x_i$，代价是$abs(a_i-x_i)$，$x_i$ != $x_j$ ($i$!=$j$)。求n个数最小的代价和。

输入

第一行T组数据
每组数据第一行一个n (1 <= n <= 200)，第二行n个数$a_i$ (1 <= $a_i$ <= n)。
T组数据总n不超过200

输出

n个数最小的代价和。

样例

输入

6
6
4 2 4 4 5 2
7
7 7 7 7 7 7 7
1
1
5
5 1 2 4 3
4
1 4 4 4
21
21 8 1 4 1 5 21 1 8 21 11 21 11 3 12 8 19 15 9 11 13

输出

4
12
0
0
2
21

样例1： x = 3,1,5,4,6,2；最小代价：|4−3|+|2−1|+|4−5|+|4−4|+|6−5|+|2−2|=4.
样例2： x = 4,5,6,7,8,9,10.
样例3： x = 1.
样例4： x = 5,1,2,4,3.
样例5： x = 1,3,4,5.

思路

(DP) $O(n^3)$

$dp[i][j]$: 第i个数的 $x_i$ 取j时的前i个数的最小代价和。
$dp[i][z]$ = min{ $dp[i - 1][j] + abs(a[i] - z)$ }

好像有一些大佬写了费用流…

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;
int dp[217][417],a[217];

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=1;i<=n;++i) for(int j=0;j<=400;++j) dp[i][j]=INF;
        sort(a+1,a+1+n);
        for(int i=1;i<=n;++i){
            for(int j=i-1;j<=n*2;++j){
                for(int z=j+1;z<=n*2;++z){
                    dp[i][z]=min(dp[i-1][j]+(int)abs(a[i]-z),dp[i][z]);
                }
            }
        }
        // for(int i=1;i<=n;++i) {
        //  for(int j=1;j<=2*n;++j) 
        //      if(dp[i][j]>=INF) printf(" x ");
        //      else printf("%2d ",dp[i][j]);
        //      puts("");
        // }
        int ans=INF;
        for(int i=n;i<=n*2;++i) ans=min(dp[n][i],ans);
        printf("%d\n",ans);

    }
}

/*
200
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200
*/