CF1437C Chef Monocarp

发布于 2020-10-28  39 次阅读


CF1437C

Description

n到菜品被放入了一个烤炉中,每到菜品都有一个最佳取出的时间t_i。现在按照一定顺序把菜品从烤炉中取出,每到菜品都有可能因为不在最佳时间被取出而造成不美味,定义这个不美味度为|T-t_i|,其中T是取出的时刻。求把所有菜品都取出来的最小不美味度。

Solution

f[i][j]表示在i时刻拿出了前j个菜品可以获得的最小不美味度

考虑暴力DP

若不选,则f[i][j] = min{ f[i-1[j]}

如果选的话,那么f[i][j] = min{f[i-1][j-1] + |i - t[k]|}

按照现在的方式DP,每次都要枚举最后选的那个菜品k,考虑怎么优化它

贪心地选,我们肯定希望t[i]比较小的物品在比较靠前的时间就被选中了,这样会比较优

如果我们对所有t[i]进行排序,那么选出的菜品将会是连续的一段。也就是说,最后一个还未被选中的菜品一定当前要选的

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 6e2 + 5;
const int inf = 0x7f7f7f7f;

int T, n;
int a[SIZE], f[SIZE][SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    T = read();
    while (T --) {
        n = read();
        for (int i = 1; i <= n; ++ i) a[i] = read();
        std::sort(a + 1, a + n + 1);
        memset(f, inf, sizeof(f));
        int minn = inf;
        f[0][0] = 0;
        for (int i = 1; i <= 2 * n; ++ i) {
            f[i][0] = 0;
            for (int j = 1; j <= std::min(i, n); ++ j) {
                f[i][j] = std::min(f[i][j], f[i - 1][j]);
                f[i][j] = std::min(f[i - 1][j - 1] + abs(i - a[j]), f[i][j]);
            }
            if (i >= n) minn = std::min(minn, f[i][n]);
        }
        printf("%d\n", minn);
    }
    return 0;
}


朴实沉毅