题目连接: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;
}
分享到:
相关推荐
该项目是通过引导的。 可用脚本 在项目目录中,可以运行: npm start 在开发模式下运行应用程序。 打开在浏览器中查看它。 如果您进行编辑,则页面将重新加载。 您还将在控制台中看到任何棉绒错误。...
Site-跆拳道-ITF 我的第一个版本化项目
taekwondo scooter http://www.taekwondo-rudersberg.de 参观Rudersberg的Taekwondoschule并体验关闭,有多少享受可以带来武术活动。 了解纪律,野心和无与伦比的社区感觉。 适合儿童,青少年和成人。 体育优惠...
教练工作手册 ... 跆拳道(TAEKWONDO),起源于韩国,是一种手脚并用的传统搏击格斗术,也是一项紧张激烈、惊险刺激的以腿法对抗为主要形式的现代竞技运动,更是一门强健体魄、磨练意志品质的高尚武道文化。
Teifi Taekwondo是一家虚构的俱乐部,位于Tedog河两岸的圣Dogmaels 小样 用户体验 新用户 目标1:作为新用户,我希望能够找到有关俱乐部主要用途的信息 目标2:作为新用户,我希望能够轻松浏览各种页面以查找所需的...