区间动态规划

石子合并

题面

有$n$堆石子排成一排，第$i$堆石子有$a_i$颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

思路

考虑最后合并的两堆石子，存在一个分界线x，其中一堆是第1堆到第x堆石子合并得到的结果，另一堆是第x+1堆石子到第n堆石子合并得到的结果；

当x确定的时候，总代价=合并第1堆石子到第x堆石子的代价+合并第x+1堆石子到第n堆石子的代价+总石子数；

对x的位置进行枚举；

递归

#include 
using namespace std;
const int N = 510;
int n, a[N], s[N];
int solve(int l, int r)
{
    if (l == r)
        return 0;
    int ans = 1 << 30;
    for (int m = l; m < r; m++)
        ans = min(ans, solve(l, m) + solve(m + 1, r));
    return ans + s[r] - s[l - 1];
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    printf("%d", solve(1, n));
    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

记忆化搜索

#include 
using namespace std;
const int N = 510;
int n, a[N], s[N], f[N][N];
int solve(int l, int r)
{
    if (f[l][r] != -1)
        return f[l][r];
    if (l == r)
        return f[l][r] = 0;
    int ans = 1 << 30;
    for (int m = l; m < r; m++)
        ans = min(ans, solve(l, m) + solve(m + 1, r));
    return f[l][r] = ans + s[r] - s[l - 1];
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    memset(f, -1, sizeof f);
    printf("%d", solve(1, n));
    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
25
26

动态规划

从小区间开始逐渐扩散到大区间。

#include 
using namespace std;
const int N = 510;
int n, a[N], s[N], f[N][N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    memset(f, 127, sizeof f);
    for (int i = 1; i <= n; i++)
        f[i][i] = 0;
    for (int i = 1; i < n; i++)             //区间的长度
        for (int j = 1; j <= n; j++)        //区间的左端点
            for (int k = j; k < j + i; k++) //枚举分界线
                f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);
    printf("%d", f[1][n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

括号序列

题面

给定一个长度为$n$的字符串$s$，字符串由 $($，$)$，$[$，$]$组成，问其中最长的合法子序列有多长？也就是说，我们要找到最大的$m$，使得存在$i_1,i_2,\dots ,i_m$ 满足$1\le i_1<i_2<\cdots <i_m\le n$并且 $s_{i_1}{s}_{i_2}\dots s_{i_m}$ 是一个合法的括号序列。

合法的括号序列的定义是：

空串是一个合法的括号序列。

若 A 是一个合法的括号序列，则 (A), [A] 也是合法的括号序列。

若 A, B 都是合法的括号序列，则 AB 也是合法的括号序列。

在区间$[i,j]$（$s_i{s}_{i+1}...s_j$）中最长合法子序列长什么样，有4种可能情况：

1. $s_i{s}_{i+1}...s_j$的最长合法子序列等于$s_{i+1}...s_j$的最长合法子序列，也就是说最左边的括号$s_i$不在当前的最长合法子序列中，问题变成了考虑区间$[i+1,j]$时的情况；
2. $s_i{s}_{i+1}...s_j$的最长合法子序列等于$s_i{s}_{i+1}...s_{j-1}$的最长合法子序列，也就是说最右边的括号$s_j$不在当前的最长合法子序列中，问题变成了考虑区间$[i,j-1]$时的情况；
3. 如果$s_i$和$s_j$匹配（$s_i$ 是左括号，$s_j$是右括号，并且它们属于同一种括号类型），那么$s_{i}A{s}_j$也是潜在的$s_i{s}_{i+1}...s_j$的最长合法子序列，其中$A$表示$s_{i+1}...s_{j-1}$的最长合法子序列，问题变成了考虑区间$[i+1,j-1]$时的情况；
4. 存在一个分界线$k$，$s_i...s_k,s_{k+1}...s_j$的最长合法子序列分别是$A$, $B$，那么$AB$也是潜在的$s_i{s}_{i+1}...s_j$的最长合法子序列，问题变成了考虑区间$[i,k]$和$[k+1,j]$时的情况；

#include 
using namespace std;
const int N = 510;
int n, f[N][N];
char str[N];
int main()
{
    scanf("%d%s", &n, str + 1);
    memset(f, 0, sizeof f);
    for (int i = 1; i < n; i++)          //区间长度
        for (int j = 1; j <= n - i; j++) //区间左端
        {
            if ((str[j] == '(' && str[j + i] == ')') || (str[j] == '[' && str[j + i] == ']'))
                f[j][j + i] = f[j + 1][j + i - 1] + 2;
            for (int k = j; k < j + i; k++) //枚举分界线
                f[j][j + i] = max(f[j][j + i], f[j][k] + f[k + 1][j + i]);
        }
    printf("%d\n", f[1][n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

石子合并2

题面

有$n$堆石子围成一个圈，第$i$堆石子有$a_i$颗，每次我们可以选择相邻的两堆石子合并，代价是两堆石子数目的和，现在我们要一直合并这些石子，使得最后只剩下一堆石子，问总代价最少是多少？

暴力

考虑一开始的圆，圆上有 n 堆石子，在相邻的石子间连边，一共有 n 条边，每次合并相邻两堆石子的时候，有一条边会消失。从开始到结束一共要合并 n - 1 次，有 n - 1 条边会消失，也就是说最后一定会有一条边没有消失；

我们可以理解成这条边一开始就不存在，现在只剩下了 n - 1 条边，问题变成了一条链的情况。

倍增

构造一个长度为 2n 的序列，它是由两个 a 数组接起来得到的。也就是说，对于前 n 个位置中的位置 i，对应了原来的第 i 堆石子，对于后 n 个位置中的位置 i，对应了原来的第 i - n 堆石子。

• 假如消失的是第 n 堆和第 1 堆石子之间的边，是不是变成了一条 1, 2, …, n 的链，最小代价为 f[1][n]；
• 假如消失的是第 1 堆和第 2 堆石子之间的边，是不是变成了一条 2,…, n, 1 的链，相当于现在序列中的第 2 到第 n + 1 个位置，最小代价为 f[2][n + 1]；
• 假如消失的是第 2 堆和第 3 堆石子之间的边，是不是变成了一条 3,…, n, 1, 2 的链，相当于现在序列中的第 3 到第 n + 2 个位置，最小代价为 f[3][n + 2]；
• …
• 假如消失的是第 n - 1 堆和第 n 堆石子之间的边，是不是变成了一条 n, 1, …, n - 1 的链，相当于现在序列中的第 n 到第 2n - 1 个位置，最小代价为f[n][2n - 1]。

我们只要在这 n 种情况中取最小值就可以啦！

#include 
using namespace std;
const int N = 260;
int n, a[2 * N], f[2 * N][2 * N], s[2 * N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[n + i] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++)
        s[i] = s[i - 1] + a[i];
    memset(f, 127, sizeof f);
    for (int i = 1; i <= 2 * n; i++)
        f[i][i] = 0;
    for (int l = 1; l < 2 * n; l++)
        for (int i = 1; i <= 2 * n - l; i++)
        {
            int j = i + l;
            for (int k = i; k < j; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }
    int ans = 1 << 30;
    for (int i = 1; i <= n; i++)
        ans = min(ans, f[i][i + n - 1]);
    printf("%d\n", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30