ABC315F - Shortcuts

这是一道关于动态规划的题目，题目要求在给定的平面上按顺序走过所有点，并且可以选择跳过一些点，求移动总距离和代价之和的最小值。

题目大意

平面上有 $n$ 个点，需要按顺序走过点 $1-n$ ，可以跳过除了点 $1$ 和点 $n$ 以外的一些点，跳过 $c$ 个点的代价是：

• $2^{c-1}$ if $c>0$
• $0$ if $c=0$ 求移动总距离和代价之和的最小值。

思路

dp[i][j] 表示到达点 $i$ 且跳过了 $j$ 个点所走的最小总距离，对于每个状态，枚举它从点 $i$ 走到的下一个点，刷表进行转移。值得一提的是，由于跳过点的代价呈指数增长，如果跳过了 $60$ 个点以上，代价显然会非常大，因此状态总数可以压缩成 $N \times 60$，转移复杂度为 $60$，总时间复杂度为 $O(N \times 60 \times 60)$。

代码

double dp[10005][170], res;
int n, K;
ll pen[66];
struct node {
    int x, y;
} a[10005];
double dist(node x, node y) {
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
int main() {

    pen[1] = 1;
    rep(i, 2, 60) pen[i] = pen[i - 1] << 1;
    scd(n);
    rep(i, 2, n) rep(j, 0, 60) dp[i][j] = 1e9;
    res = 1e9;
    rep(i, 1, n) { scdd(a[i].x, a[i].y); }
    dp[1][0] = 0.0;
    rep(i, 1, n) {
        rep(j, 0, 60) {
            rep(nx, i + 1, n) {
                int sk = j + nx - i - 1;
                if (sk > 60)
                    break;
                dp[nx][sk] = min(dp[nx][sk], dp[i][j] + dist(a[i], a[nx]));
            }
        }
    }
    rep(j, 0, 60) {
        if (j >= n)
            break;
        res = min(res, dp[n][j] + pen[j]);
    }
    pr("%.10lf", res);
    return 0;
}