UVa 10271 - Chopsticks | Sengxian's Blog

UVa 10271 - Chopsticks

#动态规划 #排序

Published on 2016-10-26

描述

有 $n(n\le 5000)$ 根筷子，长度分别为，有 $K + 8(0\le K\le 1000)$ 个客人，你需要为每个人配备 3 根筷子，设这三双筷子长度分别为 $A\le B\le C$ ，那么代价为 $(B - A)^2$ 。请问最小的代价是什么？

分析

将序列从大到小排序，不难发现，一定存在一个 $A$ 与 $B$ 都相邻的最优解，所以考虑进行 DP。
设 $dp[i][j]$ 为前 $i$ 根筷子中满足 $j$ 个人的最小代价，边界为 $dp[0][0] = 0$ 。
转移的话，考虑选不选 $i$ 这根筷子，如果不选，那么 $dp[i][j] = dp[i - 1][j]$ ，如果选，那么就要同时选 $i$ 和 $i - 1$ 这两双筷子（做 $A$ 与 $B$ ），同时需要满足 $j * 3 \le i$ 才能保证前面存在一个 $C$ ，此时 $dp[i][j] = dp[i - 2][j - 1] + (a[i - 1] - a[i])^2$ 。

思维过程：对于每个人来说， $C$ 的值只需不小于 $A$ 与 $B$ 就行了，通过巧妙的倒序排列，使得的我们在选择 $A, B$ 的时候，能够直接对 $C$ 进行选择（只需判断是否有空闲的位置就行了），从而大大降低了状态的数量。

代码

//  Created by Sengxian on 2016/10/26.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 10271 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 5000 + 3, MAX_K = 1008 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
int n, K, a[MAX_N];
ll dp[MAX_N][MAX_N];

inline void tension(ll &a, const ll &b) {
    if (b < a) a = b;
}

inline ll sqr(const int a) {
    return (ll)a * a;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    int caseNum = ReadInt();
    while (caseNum--) {
        K = ReadInt() + 8, n = ReadInt();
        for (int i = n; i >= 1; --i) a[i] = ReadInt();
        memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j * 3 <= i; ++j) {
                dp[i][j] = dp[i - 1][j];
                if (j - 1 >= 0 && i - 2 >= 0) tension(dp[i][j], dp[i - 2][j - 1] + sqr(a[i] - a[i - 1]));
            }
        printf("%lld\n", dp[n][K]);
    }
    return 0;
}

「NOIP 1999」旅行家的预算 UVa 1372 - Log Jumping