区间DP

区间 DP

P 1880 石子合并

区间 DP

判断最小值的话需要先对数组 memset(f1, 0x7f, sizeof f1), f1[i][i] = 0
最大值则不用

int f1[210][210], f2[210][210];
void solve() {
    int n;cin >> n;
    memset(f1, 0x7f, sizeof f1);
    vector<int>a(2 * n + 1), pre(2 * n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];a[n + i] = a[i];
    }
    for (int i = 1;i <= 2 * n - 1;i++)pre[i] = pre[i - 1] + a[i], f1[i][i] = 0;
    for (int i = 2;i <= n;i++) {
        for (int l = 1;l + i - 1 <= 2 * n - 1;l++) {
            int r = l + i - 1;
            for (int k = l;k < r;k++) {
                f1[l][r] = min(f1[l][r], f1[l][k] + f1[k + 1][r] + pre[r] - pre[l - 1]);
                f2[l][r] = max(f2[l][r], f2[l][k] + f2[k + 1][r] + pre[r] - pre[l - 1]);
            }
        }
    }
    int mx = -1, mi = INT_MAX;
    for (int i = 1;i <= n;i++) {
        mi = min(f1[i][i + n - 1], mi);
        mx = max(f2[i][i + n - 1], mx);
    }
    cout << mi << '\n' << mx << '\n';
}

P1775 石子合并（弱化版）

int f1[310][310];
void solve() {
    int n;cin >> n;
    memset(f1, 0x7f, sizeof f1);
    vector<int>a(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];pre[i] = pre[i - 1] + a[i], f1[i][i] = 0;
    }
    for (int i = 2;i <= n;i++) {
        for (int l = 1;l + i - 1 <= n;l++) {
            int r = l + i - 1;
            for (int k = l;k < r;k++) {
                f1[l][r] = min(f1[l][r], f1[l][k] + f1[k + 1][r] + pre[r] - pre[l - 1]);
            }
        }
    }
    cout << f1[1][n] << '\n';
}

P3146 248 G

区间 DP

int f[310][310];
void solve() {
    int n;cin >> n;
    int mx = -1;
    for (int i = 1;i <= n;i++) {
        cin >> f[i][i];mx = max(mx, f[i][i]);
    }
    for (int i = 2;i <= n;i++) {
        for (int l = 1;l + i - 1 <= n;l++) {
            int r = l + i - 1;
            for (int k = l;k < r;k++) {
                if (f[l][k] == f[k + 1][r] && f[l][k]) {
                    f[l][r] = max(f[l][r], f[l][k] + 1);
                    mx = max(mx, f[l][r]);
                }
            }
        }
    }
    cout << mx << '\n';
}

P1063 能量项链

注意：

这里的项链合并需要用到 $n + 1$ 区间长度，而 $(l, r)$ 区间中每次是需要两个一起进行操作的，则 $k \in (l, r)$

这里的 $i$ 也可以从 $3$ 开始

这里的区间合并是连续的，所以并不是 $f [l] [k] + f [k + 1] [r]$ 而是 $f [l] [k] = f [k] [r]$

int f[210][210], a[210];
void solve() {
    int n;cin >> n;
    for (int i = 1;i <= 2 * n;i++) cin >> a[i], a[i + n] = a[i];
    for (int i = 2;i <= n + 1;i++) {
        for (int l = 1;l + i - 1 <= 2 * n;l++) {
            int r = l + i - 1;
            for (int k = l + 1;k < r;k++) {
                f[l][r] = max(f[l][r], f[l][k] + f[k][r] + a[l] * a[k] * a[r]);
            }
        }
    }
    int mx = 0;
    for (int i = 1;i <= n;i++)mx = max(mx, f[i][n + i]);
    cout << mx << '\n';
}

P1005 矩阵取数游戏

本题需要用到 __int128_t 或者 __int128，表示范围为： $- 2^{127} \sim 2^{127} - 1 > 10^{38}$

这个类型不能直接输出，且在这个范围内进行位运算需要：((__int128_t)1 << m)

配套输入输出详见：long long 不够用？详解 __int128 - FReQuenter - 博客园

输出：

void print(__int128 x) {
    if (x > 9)print(x / 10);// if (x < 0)putchar('-'), x = -x;//负数使用
    putchar(x % 10 + '0');
}

由于每一行的答案是独立互不影响的，所有可以每次只针对那一行进行处理。

所以就将问题变成了 $n$ 重子问题：对一个长度为 $m$ 的数组，每次只能拿走数组首或尾的元素加入贡献为 $a_{i} \times 2^{j}$

$i$ 代表首或尾元素的下标， $j$ 代表第几次拿走元素。

易得：剩下的下标区间一定是连续且唯一的。

若当前剩下的下标区间是 $[l, r]$ ，则可能是 $[l - 1, r]$ 将下标为 $l - 1$ 的元素拿走或 $[l, r + 1]$ 将下标为 $r + 1$ 的元素拿走

转移方程：

f_{i, j} = max {f_{i, j}, f_{i - 1, j} + a_{i - 1} \cdot 2^{m - j + i - 1}, f_{i, j + 1} + a_{j + 1} \cdot 2^{m - j + i - 1}}

本题的要求是要将全部元素都取完，即最终是空区间。这里只能到长度为 1 的区间，然后手动由长度为 1 的区间加上相应贡献即为这个数组全部贡献。

__int128_t f[85][85];
int a[85];
void solve() {
    int n, m;cin >> n >> m;
    __int128_t ans = 0;
    while (n--) {
        memset(f, 0, sizeof f);
        for (int i = 1;i <= m;i++) cin >> a[i];
        for (int i = 1;i <= m;i++) {
            for (int j = m;j >= i;j--) {
                f[i][j] = max(f[i][j], f[i - 1][j] + ((__int128_t)1 << (m - j + i - 1)) * a[i - 1]);
                f[i][j] = max(f[i][j], f[i][j + 1] + ((__int128_t)1 << (m - j + i - 1)) * a[j + 1]);
            }
        }
        __int128_t mx = 0;
        for (int i = 1;i <= m;i++) {
            mx = max(mx, f[i][i] + ((__int128_t)1 << m) * a[i]);
        }
        ans += mx;
    }
    print(ans);
}

P 4170 涂色

易得：当区间长度为 1 时，需要涂的次数为 1

若区间 $[l, r] (r > l)$ 满足：

$s [l] = s [r]$ ，则这个时候涂 $l$ 可将 $r$ 一起涂了，同理涂 $r$ 可将 $l$ 一起涂了。即： $f [l] [r] = f [l] [r - 1] or f [l + 1] [r]$
$s [l] \neq s [r]$ ，将这段分成两部分来考虑可能会更优，将区间分为 $[l, k], [k + 1, r]$ 分别考虑

注：
memset~0x3f~1e9 memset~0x7f~~2e9

这里的 for (int i = 1, j = i + 1;j <= n;i++, j++){} 等价于 for (int i = 1;i + l <= n;i++){int j = i + l;}

int f[55][55];
void solve() {
    string s;cin >> s;int n = s.size();s = ' ' + s;
    memset(f, 0x3f, sizeof f);
    for (int i = 1;i <= n;i++)f[i][i] = 1;
    for (int l = 1;l < n;l++) {
        for (int i = 1, j = i + 1;j <= n;i++, j++) {
            if (s[i] == s[j]) {
                f[i][j] = f[i][j - 1];// f[i][j] = min(f[i + 1][j], f[i][j - 1]);
            } else {
                for (int k = i;k < j;k++) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
                }
            }
        }
    }
    cout << f[1][n] << '\n';
}

P 4302 字符串折叠

int f[110][110];
void solve() {
    string s;cin >> s;int n = s.size();s = ' ' + s;
    auto check = [&](int l, int r, int k) {
        if ((r - l + 1) % k)return;
        for (int i = l;i <= r;i++)if (s[i] != s[(i - l) % k + l])return;
        f[l][r] = min(f[l][r], f[l][l + k - 1] + 2 + (int)to_string((r - l + 1) / k).size());
        };
    memset(f, 0x3f, sizeof f);
    for (int i = 1;i <= n;i++)f[i][i] = 1;
    for (int l = 1;l <= n;l++) {
        for (int i = 1, j = i + l;j <= n;i++, j++) {
            for (int k = i;k < j;k++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
            }
            for (int k = 1;k <= j - i;k++) check(i, j, k);
        }
    }
    cout << f[1][n] << '\n';
}

P 2466 Sue 的小球

$\dots$

EXER

使得一个字符串成为一个回文串所需要添加的最少字符个数。算法讲解076【必备】区间dp-上_哔哩哔哩_bilibili