2010-1149

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== Contest 14 by ACFun - Piano ==


'''题目大意'''[[BR]]
在钢琴的52个白键上用两只手弹琴，规定每只手都要占至少5个键，而一只手最多可以弹9个键。为了弹到所有的键，需要左手或者右手的移动，每次移动的消耗为大拇指移动距离的平方根取整。给定初始时两手大拇指所在的键位，以及所有要弹的键，求最小的总消耗。

'''解法'''[[BR]]
DP即可，dp的状态需要三维，分别为当前弹到了第几个键、左手大拇指所在位置、右手大拇指所在位置。实现中为了节省空间，第一维可以用滚动数组来实现。

'''代码如下(by t!__nt)：'''
{{{
#!cpp
#include <cstdio>
#include <cstring>

const int N = 52;
const int MAXN = 60 + 1;
const int INF = 1012345678;

int SQRT[MAXN], dp[2][MAXN][MAXN], L, R, M;
bool valid[MAXN][MAXN];

inline int min(int a, int b) {
    return a < b ? a : b;
}

inline int max(int a, int b) {
    return a > b ? a : b;
}

inline int abs(int a) {
    return a < 0 ? -a : a;
}

int main() {
    for (int i = 1; i * i < MAXN; i++) SQRT[i * i] = i;
    for (int j = 2; j < MAXN; j++) {
        if (!SQRT[j]) SQRT[j] = SQRT[j - 1];
    }
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            valid[i][j] = (4 <= i && i <= 51 && 0 <= j && j <= 47 && (i < j || abs(i - j) >= 9));
        }
    }
    while (scanf("%d%d%d", &L, &R, &M) != EOF) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dp[0][i][j] = INF;
            }
        }
        dp[0][L][R] = 0;
        int t1 = 0, t2;
        for (int i = 0; i < M; i++) {
            t2 = t1 ^ 1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dp[t2][i][j] = INF;
                }
            }
            int button;
            scanf("%d", &button);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (dp[t1][i][j] == INF) continue;
                    // move left hand
                    if (i - 8 <= button && button <= i) {
                        dp[t2][i][j] = min(dp[t2][i][j], dp[t1][i][j]);
                    } else {
                        for (int ii = min(button + 8, 51); ii >= button; ii--) {
                            if (!valid[ii][j]) continue;
                            dp[t2][ii][j] = min(dp[t2][ii][j], dp[t1][i][j] + SQRT[abs(i - ii)]);
                        }
                    }
                    // move right hand
                    if (j <= button && button <= j + 8) {
                        dp[t2][i][j] = min(dp[t2][i][j], dp[t1][i][j]);
                    } else {
                        for (int jj = max(button - 8, 0); jj <= button; jj++) {
                            if (!valid[i][jj]) continue;
                            dp[t2][i][jj] = min(dp[t2][i][jj], dp[t1][i][j] + SQRT[abs(j - jj)]);
                        }
                    }
                }
            }
            t1 = t2;
        }
        int res = INF;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res = min(res, dp[t1][i][j]);
            }
        }
        printf("%d\n", res);
    }
    return 0;
}
}}}

Contest 14 by ACFun - Piano

题目大意

在钢琴的52个白键上用两只手弹琴，规定每只手都要占至少5个键，而一只手最多可以弹9个键。为了弹到所有的键，需要左手或者右手的移动，每次移动的消耗为大拇指移动距离的平方根取整。给定初始时两手大拇指所在的键位，以及所有要弹的键，求最小的总消耗。

解法

DP即可，dp的状态需要三维，分别为当前弹到了第几个键、左手大拇指所在位置、右手大拇指所在位置。实现中为了节省空间，第一维可以用滚动数组来实现。

代码如下(by t!__nt)：

#include <cstdio>
#include <cstring>
const int N = 52;
const int MAXN = 60 + 1;
const int INF = 1012345678;
int SQRT[MAXN], dp[2][MAXN][MAXN], L, R, M;
bool valid[MAXN][MAXN];
inline int min(int a, int b) {
    return a < b ? a : b;
}
inline int max(int a, int b) {
    return a > b ? a : b;
}
inline int abs(int a) {
    return a < 0 ? -a : a;
}
int main() {
    for (int i = 1; i * i < MAXN; i++) SQRT[i * i] = i;
    for (int j = 2; j < MAXN; j++) {
        if (!SQRT[j]) SQRT[j] = SQRT[j - 1];
    }
    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            valid[i][j] = (4 <= i && i <= 51 && 0 <= j && j <= 47 && (i < j || abs(i - j) >= 9));
        }
    }
    while (scanf("%d%d%d", &L, &R, &M) != EOF) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dp[0][i][j] = INF;
            }
        }
        dp[0][L][R] = 0;
        int t1 = 0, t2;
        for (int i = 0; i < M; i++) {
            t2 = t1 ^ 1;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    dp[t2][i][j] = INF;
                }
            }
            int button;
            scanf("%d", &button);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (dp[t1][i][j] == INF) continue;
                    // move left hand
                    if (i - 8 <= button && button <= i) {
                        dp[t2][i][j] = min(dp[t2][i][j], dp[t1][i][j]);
                    } else {
                        for (int ii = min(button + 8, 51); ii >= button; ii--) {
                            if (!valid[ii][j]) continue;
                            dp[t2][ii][j] = min(dp[t2][ii][j], dp[t1][i][j] + SQRT[abs(i - ii)]);
                        }
                    }
                    // move right hand
                    if (j <= button && button <= j + 8) {
                        dp[t2][i][j] = min(dp[t2][i][j], dp[t1][i][j]);
                    } else {
                        for (int jj = max(button - 8, 0); jj <= button; jj++) {
                            if (!valid[i][jj]) continue;
                            dp[t2][i][jj] = min(dp[t2][i][jj], dp[t1][i][j] + SQRT[abs(j - jj)]);
                        }
                    }
                }
            }
            t1 = t2;
        }
        int res = INF;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res = min(res, dp[t1][i][j]);
            }
        }
        printf("%d\n", res);
    }
    return 0;
}