virtualjudge地址
题意
有
1
1
1到
n
n
n，
n
n
n个点。设计一条路线从
1
1
1开始走到
n
n
n，再从
n
n
n走回
1
1
1，除点
1
1
1经过
2
2
2次以外，其他点能且只能经过
1
1
1次。
现给你点的个数
n
n
n，和每个点的横纵坐标
x
i
x_i
xi,
y
i
y_i
yi，问在此规则下最短路径为多少？
思路
可以将问题看成两个人从
1
1
1出发，最终都走到
n
n
n的最短路，同时每个点都要被第一个人或第二个人的其中一人经过。
所以可以设计状态为
D
P
(
i
,
j
)
DP(i,j)
DP(i,j)为计算两个人从第
i
i
i个点和第
j
j
j个点走到第
n
n
n个点的最短路程。
设
s
s
s点是
i
i
i点，
j
j
j点中进度最快的点。而由于每个点都要走过，则在第一个点到
s
s
s点后的每个点走过的前提下，
D
P
(
i
,
j
)
DP(i,j)
DP(i,j)的下一个状态只能是两个人中的其中一个走到第
s
s
s +
1
1
1点，否则就会存在没有经过的点。然后计算继续
D
P
(
s
+
1
,
i
DP(s+1,i
DP(s+1,i
o
r
or
or
j
)
j)
j)的状态，
i
i
i
o
r
or
or
j
j
j取决于未选择移动的是哪个的点。
因此为了方便设计算法，我们可以将进度快的点写在前面，设点
a
a
a到点
b
b
b的距离为
d
i
s
t
[
a
]
[
b
]
dist[a][b]
dist[a][b]，就可以得出状态转移方程：
DP(i,j) = min( DP(i+1,j) + dist[i+1][i], DP(i+1,i) + dist[i+1][j] )
Accepted Code
#include <bits/stdc++.h>
using namespace std
;
#define db double
#define ll long long
#define inf 0x3f3f3f3f
#define s(a, n) memset(a, n, sizeof(a))
#define debug(a) cout << '#' << a << '#' << endl
#define rep(l, a, b) for (register ll l = a; l < b; ++l)
#define per(l, a, b) for (register ll l = a; l >= b; --l)
#define _ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _forit(i, c) \
for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
bool fi
= true;
const unsigned long long MOD
= 1e9 + 7;
inline ll
gcd(ll a
, ll b
) { return (b
== 0 ? a
: gcd(b
, a
% b
)); }
int n
;
db dp
[1005][1005], dist
[1005][1005];
int vis
[1005][1005];
struct node
{
int x
, y
;
} no
[1005];
db
DP(int i
, int j
) {
if (i
== n
- 2) return dp
[i
][j
] = dist
[n
- 1][i
] + dist
[n
- 1][j
];
if (vis
[i
][j
]) return dp
[i
][j
];
vis
[i
][j
] = 1;
return dp
[i
][j
] = min(DP(i
+ 1, i
) + dist
[i
+ 1][j
],
DP(i
+ 1, j
) + dist
[i
+ 1][i
]);
}
int main() {
while (~scanf("%d", &n
)) {
s(vis
, 0);
rep(i
, 0, n
) scanf("%d%d", &no
[i
].x
, &no
[i
].y
);
rep(i
, 0, n
- 1) {
rep(j
, i
+ 1, n
) {
dist
[j
][i
] =
sqrt((db
)((no
[j
].x
- no
[i
].x
) * (no
[j
].x
- no
[i
].x
)) +
(db
)((no
[j
].y
- no
[i
].y
) * (no
[j
].y
- no
[i
].y
)));
}
}
printf("%.2lf\n", DP(1, 0) + dist
[1][0]);
}
}
