CF1437C Chef Monocarp

2020 年 10 月 28 日

1917 次浏览

835字数

[CF1437C](https://www.luogu.com.cn/problem/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

```cpp
#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;
}
```

最后修改：2021 年 09 月 04 日