一本通 提高篇—区间类动态规划

#10147. 「一本通 5.1 例 1」石子合并

题目描述

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

选择一种合并石子的方案，使得做 n-1 次合并得分总和最大。
选择一种合并石子的方案，使得做 n-1 次合并得分总和最小。

输入格式

输入第一行一个整数 n，表示有 n 堆石子。

第二行 n 个整数，表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

样例

输入

4
4 5 9 4

输出

43
54

数据范围与提示

对于100% 的数据，有1<=n<=200 。

代码

#include "bits/stdc  .h"
using namespace std;
int n,sum[409],a[409];//a开[1,2*n-1],a[n i]=a[i], 
int dp1[400][409],dp2[400][409];
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i  )
	{
		cin>>a[i];
		a[n i]=a[i];
	}
	for(int i=1;i<2*n;i  )
	{
		sum[i]=sum[i-1] a[i];
		dp1[i][i]=0;
		dp2[i][i]=0;
	}
	for(int l=2;l<=n;l  )//长度
	{
		for(int i=1;i<2*n&&i l-1<2*n;i  )//开头 
		{
			int j=i l-1;//结尾
			dp1[i][j]=0X3f3f3f;
			dp2[i][j]=0;
			for(int ii=i;ii<=j;ii  )
			{
				dp1[i][j]=min(dp1[i][j],dp1[i][ii] dp1[ii 1][j]);
				dp2[i][j]=max(dp2[i][j],dp2[i][ii] dp2[ii 1][j]);
			} 
			dp1[i][j] =sum[j]-sum[i-1];
			dp2[i][j] =sum[j]-sum[i-1];
		 } 
	} 
	int maxx=0,minn=0X3f3f3f; 
	for(int i=1;i<=n;i  )
	{
		minn=min(minn,dp1[i][i n-1]);
		maxx=max(maxx,dp2[i][i n-1]);
	}
	cout<<minn<<endl<<maxx;
}

#10148. 「一本通 5.1 例 2」能量项链

题目描述

原题来自：NOIP 2006

在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 n 颗能量珠。能量珠是一颗有头标记和尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记必定等于后一颗珠子的头标记。因为只有这样，通过吸盘——Mars 人吸收能量的器官的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可被吸盘吸收的能量。如果一颗能量珠头标记为m ，尾标记为 r，后一颗能量珠头标记为 r，尾标记为 n，则聚合后释放出 m * r * n Mars单位的能量，新珠子头标记为m ，尾标记为n 。

当需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不一样的。请设计一个聚合顺序使得一串珠子聚合后释放出的总能量最大。

例如，设N=4 ，四颗珠子头标记与尾标记分别为(2,3) , (3,5) , (5,10) , (10,2) 。我们用记号 @ 表示两颗珠子的聚合操作， (j@k) 表示j,k两颗珠子聚合后释放出的能量，则4,1两颗珠子聚合后所释放的能量为(4@1)=10 * 2 * 3 = 60，这一串项链可以得到最优值的一个聚合顺序所释放出的总能量为 (((4@1)@2)@3)=10 * 2 * 3 10 * 3 * 5 10 * 5 *10=710

现在给你一串项链，项链上有 n 颗珠子，相邻两颗珠子可以合并成一个，合并同时会放出一定的能量，不同珠子合并放出能量不相同，请问按怎样的次序合并才能使得释放的能量最多？

输入格式

第一行一个正整数 n

第二行 n 个不超过1000 的正整数，第 i(1<=i<=n) 个数为第 i 颗珠子的头标记，当 i != n 时第 i 颗珠子的尾标记等于第 i 1 颗珠子的头标记，当i=n 时第 i 颗珠子的尾标记等于第1 颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放在桌面上，不要出现交叉，随机指定一颗珠子为第一颗珠子，按顺时针确定其它珠子的顺序。

输出格式

输出只有一行，一个不超过2.1*10⁹ 的正整数，表示最优聚合顺序所释放的能量。

样例

输入

4
2 3 5 10

输出

710

数据范围与提示

对于 100% 的数据，4<=n<=100。

代码

#include "bits/stdc  .h"
using namespace std;
int dp[209][209];
int a[209];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i  )
	{
		cin>>a[i];
		a[i n]=a[i];
	}
	for(int l=1;l<=n;l  )//长度 
		for(int i=1;i<2*n&&i l<2*n;i  )//第i个珠子 
		{
			int j=i l;//第j个珠子 
			for(int k=i;k<j;k  )
				dp[i][j]=max(dp[i][j],dp[i][k] dp[k 1][j] a[i]*a[k 1]*a[j 1]);
		}
	 int m=0;
	 for(int i=1;i<=n;i  )
	 	m=max(m,dp[i][i n-1]);
	cout<<m;
}

#10149. 「一本通 5.1 例 3」凸多边形的划分

不会

#10150. 「一本通 5.1 练习 1」括号配对

题目描述

Hecy 又接了个新任务：BE 处理。BE 中有一类被称为 GBE。

以下是 GBE 的定义：

1.空表达式是 GBE
2.如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
3.如果 A 与 B 都是 GBE，那么 AB 是 GBE
下面给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。

输入格式

输入仅一行，为字符串 BE。

输出格式

输出仅一个整数，表示增加的最少字符数。

样例

输入

[])

输出

1

数据范围与提示

对于 100% 的数据，输入的字符串长度小于 100。

代码

#include "bits/stdc  .h"
using namespace std;
char a[109];
int dp[109][109];
int main()
{
	cin>>a;
	int len=strlen(a);
	for(int l=1;l<len;l  )//l 1为长度
		for(int i=0;i l<len;i  )//开头
		{
			int j=i l;//结尾
			if((a[i]=='('&&a[j]==')')||(a[i]=='['&&a[j]==']'))
				dp[i][j]=dp[i 1][j-1] 2;
			for(int k=i;k<=j-1;k  )//找最优值
				dp[i][j]=max(dp[i][j],dp[i][k] dp[k 1][j]);	
		}
	cout<<len-dp[0][len-1];
 } 

#10151. 「一本通 5.1 练习 2」分离与合体

不会

#10152. 「一本通 5.1 练习 3」矩阵取数游戏

题目描述

原题来自：NOIP 2007

帅帅经常和同学玩一个矩阵取数游戏：对于给定的 n*m 的矩阵，矩阵中每个元素 aij 均为非负整数。游戏规则如下：

1. 每次取数时必须从每行各取走一个元素，共 n 个，m 次取完所有元素。
2. 每次取走的各个元素只能是该元素所在行行首或行尾。
3. 每次取数都有一个的分值，为每行取数得分之和，每行取数得分=被取走元素值*pow(2,i)，其中 i 表示第 i 次取数，从 1 开始计数。
4. 游戏结束时，总得分为 m 次取数得分之和。
   帅帅想让你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入格式

输入包括 n 1 行。 第一行两个空格隔开的正整数 n,m 接下来 n 行每行 m 个用空格隔开的整数。

输出格式

输出为一个整数，为所输入矩阵取数后的最大得分

样例 1

输入

2 3
1 2 3
3 4 2

输出

82

第一次：第一行取行首元素 ，第二行取行尾元素，本次得分为 1* 2¹ 2 * 2¹=6 ；第二次：两行均取行首元素，本次得分为 2 * 2² 3 * 2²=20 ； 第三次：本次得分为 3 * 2³ 4 * 2³=56，总得分为 6 20 56=82。

样例 2

输入

1 4
4 5 0 5

输出

122

样例 3

输入

2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67

输出

316994

数据范围与提示

对于60% 的数据，1<n,m<=30，答案不超过 10¹⁶；
对于 100% 的数据1<=n,m<=80,0<=aij<=1000。

思路

我们一行一行的算，每行从里向外推（从外向里推答案不对，你得的样例2答案不对），这儿要用高精度计算，long long 爆表，可以引用__int128

__int128

__int128 就是占用128字节的整数存储类型。由于是二进制，范围就是 −2¹²⁷ ~ 2¹²⁷−1，如果使用了 unsigned __int128，则范围变成 0 ~ 2¹²⁸，即约39位数！
由于 __int128 仅仅是 GCC 编译器内的东西，不在 C 98/03/11/14/17/20 标准内，且仅 GCC4.6 以上64位版本支持，很多配套都没有，只有四则运算功能 所以要自己写输入输出。使用方法与 int long long 无异：

代码

#include "bits/stdc  .h"
using namespace std;
typedef unsigned long long ull;
int a[90][90];
__int128 dp[90][90];
//使用__int128可以实现高精度运算，但是这种大整数无法使用printf输出结果，所以需要手写函数输出
void print(__int128 x)
{
	if(x>9)
		print(x/10);
	putchar(x '0');
}
int main()
{
	int n,m;
	__int128 sum=0;
	cin>>n>>m;
	for(int i=1; i<=n; i  )
		for(int j=1; j<=m; j  )
			cin>>a[i][j];
	for(int i=1; i<=n; i  )
	{
		int l=0;
		for(int k=m; k>=1; k--,l  )
			for(int j=1; j l<=m; j  )
				dp[j][j l]=max(dp[j][j l-1] a[i][j l],dp[j 1][j l] a[i][j])*2;
		sum =dp[1][m];
	}
	print(sum);
	return 0;
}

这篇好文章是转载于：学新通技术网