本文主要是介绍uva 1534 - Taekwondo(dp+贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接：uva 1534 - Taekwondo
题目大意：有两组什么东西，题目背景有点忘记了，就是给出两组数，两组个数分别为n，m，要求找出min(n,m)对数，每个数最多最多选一次，使得这min(n,m)对数ai,bi，ai-bi的绝对值之和最小。
解题思路：贪心，将两组数分别排序，然后dp[i][j]表示i对，匹配到j时候的最优解。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;
const int N = 505;int n, m;
double cn[N], cm[N], dp[N][N];void init () {scanf("%d%d", &n, &m);for (int i = 0; i < n; i++)scanf("%lf", &cn[i]);for (int i = 0; i < m; i++)scanf("%lf", &cm[i]);sort(cn, cn + n);sort(cm, cm + m);if (n > m) {double tmp[N];memcpy(tmp, cm, m*sizeof(double));memcpy(cm, cn, n*sizeof(double));memcpy(cn, tmp, m*sizeof(double));swap(n, m);}
}double solve () {dp[0][0] = fabs(cn[0] - cm[0]);for (int i = 1; i < m; i++)dp[0][i] = min (fabs(cn[0]-cm[i]), dp[0][i-1]);for (int i = 1; i < n; i++) {dp[i][i] = dp[i-1][i-1] + fabs(cn[i]-cm[i]);for (int j = i+1; j < m; j++)dp[i][j] = min (dp[i-1][j-1] + fabs(cn[i] - cm[j]), dp[i][j-1]);}return dp[n-1][m-1];
}int main () {int cas;scanf("%d", &cas);while (cas--) {init ();printf("%.1lf\n", solve());}return 0;
}
这篇关于uva 1534 - Taekwondo(dp+贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
