【题解】2021提高组十连测day4 n^3过一万

发表于 分类于 阅读次数： Valine： 本文字数： 346 阅读时长 ≈ 1 分钟

题目链接（正睿）

题目大意

给定含有个元素的数组，现在要选择两个相邻的元素删除，那么代价为（给出）。

用轮将所有元素删完，问代价最少是多少。

分析

二分答案，考虑使用区间。表示区间在枚举的最小代价下可不可行。如果可行，可行，那么可行。在转移的时候，让即可。时间复杂度是，使用优化，时间复杂度，其中约为。

实现

先二分枚举答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
    int L = 1e8, R = -1e8;
    n = read();
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j += 2) {
            a[i][j] = read();
            R = max(R, a[i][j]);
            L = min(L, a[i][j]);
        }
    }
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (check(mid)) R = mid - 1;
        else L = mid + 1;
    }
    cout << L;
    return 0;
}

核心代码，函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bitset<N> f[N];

inline bool check(int x) {
    for (int i = 1; i <= n; i++) {
        f[i].reset();
        if (a[i][i + 1] <= x) {
            f[i][i + 1] = true;
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i + 1; j <= n; j += 2) {
            if (f[i][j]) {
                f[i] |= f[j + 1];
            }
        }
        for (int j = i + 1; j <= n; j += 2) {
            if (f[i + 1][j - 1] && a[i][j] <= x) {
                f[i][j] = true;
                f[i] |= f[j + 1];
            }
        }
    }
    return f[1][n];
}