【题解】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];
}