week12-作业（动态规划）

C - 必做题 - 3

东东每个学期都会去寝室接受扫楼的任务，并清点每个寝室的人数。
每个寝室里面有ai个人(1<=i<=n)。从第i到第j个宿舍一共有sum(i,j)=a[i]+…+a[j]个人
这让宿管阿姨非常开心，并且让东东扫楼m次，每一次数第i到第j个宿舍sum(i,j)
问题是要找到sum(i1, j1) + … + sum(im,jm)的最大值。且ix <= iy <=jx和ix <= jy <=jx的情况是不被允许的。也就是说m段都不能相交。
注：1 ≤ i ≤ n ≤ 1e6 , -32768 ≤ ai ≤ 32767 人数可以为负数。。。。(1<=n<=1000000)
Input
输入m，输入n。后面跟着输入n个ai 处理到 EOF
Output
输出最大和
Sample Input

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

Sample Output

6
8 

思路：

最大m区间和的问题
序列有n个数，选择m个不交叉的子序列，相加找出来最大值。dp[][]为前j个数取了i段的最大和。
利用状态转移方程：dp[ i ][ j ] = max(dp[ i-1 ][ k ] + a[ j ]，dp[ i ][ j-1 ] + a[ j ]) (i-1 <= k <= j-1)
与最后一段合并是dp[ i ][ j-1 ] + a[ j ]，成为新的一段dp[ i-1 ][ k ] + a[ j ]。
k的那个循环其结果可以由上一次循环j的时候算出来也就是dp[i][j]只需要知道dp[i][j-1]和dp[i-1][k]的最大值，因此可以用一维数组。

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int a[1000010],b[1000010],c[1000010];
int main()
{
	int m, n;
	int maxt;
	while (cin >> m >> n)
	{
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		memset(b, 0, sizeof(b));
		memset(c, 0, sizeof(c));
		for (int i = 1; i <= m; i++)
		{
			maxt = -10000000;
			for (int j = i; j <= n; j++)
			{
				b[j] = max(b[j - 1], c[j - 1]) + a[j];
				c[j - 1] = maxt;
				maxt = max(maxt, b[j]);
			}
		}
		cout << maxt << endl;
	}
}

D - 选做题 - 1

题意：

我们给出以下“正则括号”序列的归纳定义:
空序列是一个普通的括号序列，
如果s是一个正则方括号序列，那么(s)和[s]是正则方括号序列，并且
如果a和b是正则中括号序列，那么ab就是一个正则中括号序列。
没有其他序列是一个普通的括号序列
例如，下面所有的字符序列都是正则括号序列:
(), [], (()), ()[], ()[()]
而下列字符序列不是:
(, ], )(, ([)], ([(]
给定一个括号序列字符a1a2…an，你的目标是找到最长的普通括号序列的长度是s的子序列。
也就是说，你希望找到最大的m，使得指数i1, i2，…，im中的1≤i1 <i2 & lt;…& lt;im≤n, ai1ai2…aim是一个规则的括号序列。
给定初始序列([([]])，子序列中最长的正则括号为[([])]
input
输入测试文件将包含多个测试用例。每个输入测试用例由一行组成，其中只包含字符(、)、[和];每个输入测试的长度都在1到100之间。文件结束由包含单词“end”的行标记，不应该被处理。
output
对于每个输入情况，程序应该将最长的可能的正则括号子序列的长度打印在一行上。
Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

思路：

对于长度为1的串一定为1，长度为0的串一定为0
对于子序列可以设状态转移方程 f[i][j]=min{f[i][k]+f[k+1[[j]}(i<=k<j)

1对于[]:f[i][j]=min{f[i+1][j-1]}即两边同时缩减开始
2对于[或者( f[i][j]=min{f[i+1][j]+1}
3对于]或者）f[i][j]=min{f[i][j-1]+1}
对于上述的所有情况取出最小值就是最终的结果f[i][j]

代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int main()
{
	string s;
	int a[110][110];
	cin >> s;
	while (s != "end")
	{
		memset(a, 0, sizeof(a));
		for (int i = 2; i <= s.size(); i++)
		{
			for (int j = 0; j < s.size() - i + 1; j++)
			{
				int t = j + i - 1;
				if ((s[j] == '(' && s[t] == ')') || (s[j] == '[' && s[t] == ']'))
					a[j][t] = a[j + 1][t - 1] + 2;
				for (int x = j; x < t; x++)
					a[j][t] = max(a[j][t], a[j][x] + a[x + 1][t]);
			}

		}
		cout << a[0][s.size() - 1] << endl;
		cin >> s;
	}
}