首页 > 代码库 > hdu 4824 Disk Schedule(双调欧几里得旅行商问题)
hdu 4824 Disk Schedule(双调欧几里得旅行商问题)
题目链接:hdu 4824 Disk Schedule
题目大意:中文题。
解题思路:需要的时,很明显每到一层是要读取一次数据的,但是因为需要返回00,所以有些层的数据可以在返回的过程中读取会较优。于是转化成了双调欧几里得旅行商问题。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f;
int n, p, d[N], dp[N][N];
int dis (int a, int b) {
int tmp = abs(d[a] - d[b]);
return min(tmp, 360 - tmp);
}
void init () {
int a;
scanf("%d", &n);
d[1] = 0;
for (int i = 2; i <= n + 1; i++) {
scanf("%d%d", &a, &d[i]);
if (i == n + 1)
p = a;
}
dp[2][1] = dis(1, 2);
}
int solve () {
for (int i = 3; i <= n + 1; i++) {
dp[i][i-1] = INF;
for (int j = 1; j < i-1; j++) {
dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));
dp[i][j] = dp[i-1][j] + dis(i, i-1);
}
}
int ans = INF;
for (int i = 1; i <= n; i++)
ans = min(ans, dp[n+1][i] + dis(n+1, i));
return ans;
}
int main () {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
init();
printf("%d\n", solve() + p * 800 + 10 * n);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。