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

发表于 分类于 阅读次数： Valine：

题目链接（正睿）

题目大意

给定含有$n$个元素的数组$a$，现在要选择两个相邻的元素$(i,j)$删除，那么代价为$cost(i,j)$（给出）。

用$\frac{n}{2}$轮将所有元素删完，问代价最少是多少。$n\le 4000$

分析

二分答案，考虑使用区间$\text{dp}$。$dp(l,r)$表示区间$[l,r]$在枚举的最小代价下可不可行。如果$dp(l,r)$可行，$dp(l-1,k)$可行，那么$dp(l,k)$可行。在转移的时候，让$dp(l,i)|=dp(r+1,i)$即可。时间复杂度是$O(n^3 \log n)$，使用$\text{bitset}$优化，时间复杂度$O(n^3/w\log n)$，其中$w$约为$64$。

实现

先二分枚举答案：

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

核心代码，$check$函数：

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