洛谷1103 书本整理

原题链接

\(DP\)水题，但我用了个三维数组。。在某谷看到的题解全是二维的。。不过反正能\(A\)，管它呢。

定义\(f[i][j][k]\)表示前\(i\)本书中不选\(j\)本，且最后一本选的书的下标为\(k\)。设\(a[i]\)表示第\(i\)本书的宽度，\(m\)表示最多能不选几本，\(abs()\)为绝对值。
于是有状态转移方程：
\[f[i][j][i] = \min \{ f[i - 1][j][k] + abs(a[i] - a[k]) \},(i = 2 \to n, j = 0 \to \min\{ i - 1, m \}, k = i - 1 \to i - j - 1) \qquad \text{选第} i \text{本书}\]
\[f[i][j][k] = f[i - 1][j - 1][k],(j > 0,\text{其它同上})\qquad \text{不选第} i \text{本书}\]
初始化\(f[i][i - 1][i] = 0, (i = 1 \to m + 1)\)，其它为\(0\)。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
struct bk {
    int h, t;
};
bk a[N];
int f[N][N][N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
bool comp(bk x, bk y) { return x.h < y.h; }
inline int jd(int x) { return x < 0 ? -x : x; }
inline int minn(int x, int y) { return x < y ? x : y; }
int main()
{
    int i, j, k, n, m, o, ans = 1e9;
    n = re(); m = re();
    for (i = 1; i <= n; i++)
        a[i].h = re(), a[i].t = re();
    sort(a + 1, a + n + 1, comp);
    memset(f, 60, sizeof(f));
    for (i = 1; i - 1 <= m; i++)
        f[i][i - 1][i] = 0;
    for (i = 2; i <= n; i++)
        for (j = 0, o = minn(i - 1, m); j <= o; j++)
            for (k = i - 1; k >= i - j - 1; k--)
            {
                f[i][j][i] = minn(f[i][j][i], f[i - 1][j][k] + jd(a[i].t - a[k].t));
                if (j)
                    f[i][j][k] = f[i - 1][j - 1][k];
            }
    for (i = 1; i <= n; i++)
        ans = minn(ans, f[n][m][i]);
    printf("%d", ans);
}

洛谷1103 书本整理

原文：https://www.cnblogs.com/Iowa-Battleship/p/10473296.html