8.3 动态规划1:线性dp、背包问题,区间 3
石子合并
题目描述:
将n堆石子绕圆形操场排放,现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数记做该次合并的得分。 请编写一个程序,读入堆数n及每堆的石子数,并进行如下计算: 选择一种合并石子的方案,使得做n-1次合并得分总和最大。 选择一种合并石子的方案,使得做n-1次合并得分总和最小。
整体思路:(假设是求最大值)我们去枚举每个小区间的分隔点k,f[i][j]表示的是从第i个数到第j个数合并能够获得的最大值,f[i][j] = max(f[i][j],f[i][k] + f[k+1][j] + sum[j] - sum[i - 1]),f[i][k] + f[k+1][j]表示的是两个被分开的小区间的值,而这两个小区间合并的大小就是这个大区间的前缀和。
注意事项:
- 无论是求最大值还是最小值,都应该把f[i][i]附成0,因为把自己和自己合并能够获得的值是0。
- 求最大值的时候应该把除了f[i][i]以外的值附成负无穷(最小值时就附成正无穷)。
示例代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 300;
int f[N][N],g[N][N];
int a[N];
int sum[N];
int main()
{
memset(f,10,sizeof f);//最小值
memset(g,-10,sizeof g);
int n;
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i],a[i + n] = a[i];
for(int i = 1;i <= n * 2;i++) sum[i] = sum[i - 1] + a[i],f[i][i] = 0,g[i][i] = 0;
for(int len = 2;len <= n;len++)
{
for(int l = 1;l + len - 1 <= n * 2;l++)
{
int r = l + len - 1;
for(int k = l;k < r;k++)
{
f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);
g[l][r] = max(g[l][r],g[l][k] + g[k + 1][r] + sum[r] - sum[l - 1]);
}
}
}
int maxv = -114514,minv = 114514;
for(int i = 1;i <= n;i++)
{
maxv = max(maxv,g[i][i + n - 1]);
minv = min(minv,f[i][i + n - 1]);
}
cout << minv << endl << maxv << endl;
return 0;
}
具体运行结果:
括号匹配
题目描述:
输入若干个字符串包含‘(’ ‘)’‘[’ ‘]’四种类型的符号,问这个字符串最多有多少个匹配的括号。
分析:
写的时候有点急了,没有仔细去分析。首先对整个长度的区间去动态规划,是一个典型的区间dp问题。
- 如果左端点等于右端点,那么说明只有单独的一个元素,则返回该区间有0个匹配的括号。(f[i][j]表示的是从i到j最多有多少个匹配的括号,我感觉区间的dp其实很细致的把每种情况都考虑到了,比较巧妙又比较暴力)
- 写的时候推荐记忆化搜索,如果f[i][j]已经存在了,那就不用去算了,减少算法的复杂程度。
- 若前面的情况都不满足的话,说明f[i][j]并不存在,那么只可能有两种求值的情况:一. 是在除了该位置的地方找最大的匹配数,二.在包括该位置的地方找最大匹配的括号数,对于这种情况只要枚举匹配的右括号的位置并且接着递归就可以解决。
具体代码:
#include<iostream>
#include<cstring>
using namespace std;
string s;
int f[200][200];
int dp(int l,int r)
{
if(r <= l) return f[l][r] = 0;
if(f[l][r] != 0)return f[l][r];
f[l][r] = dp(l + 1,r);
for(int i = l + 1; i <= r;i++)
{
if(s[l] == '(' && s[i] == ')' || s[l] == '[' && s[i] == ']')
f[l][r] = max(f[l][r],dp(l + 1,i - 1) + dp(i + 1,r) + 2);
}
return f[l][r];
}
int main()
{
ios::sync_with_stdio(false);
//string s;
while(cin >> s)
{
if(s == "end") break;
int len = s.length();
memset(f,0,sizeof f);
//cout << f[0][len - 1] <<endl;
cout << dp(0,len - 1) << endl;
}
return 0;
}