CF1437 简要题意及题解

tony102

2020 年 10 月 29 日

1061 次浏览

暂无评论

1016字数

总结

A

题意

$\exists x$, 对于$\forall i \in [l,r]$，要求$i\ mod\ x \geq \frac{x}{2}$,判断是否存在这样的$x$

B

题意

给定一个长度为偶数的$01$串，每次可以选定一个子串进行翻转操作。要求最后翻转成一个$0,1$交替的串（只有$0101\dots01$和$1010\dots10$类型的串是合法的串）。求最少的操作次数。

C

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;
}