dp基础专题五

自用笔记算法

dp专题五

最优矩阵链乘问题

题目要求

一个n×m阶矩阵和一个m×p阶矩阵连乘 运算量是nmp
有n个矩阵链乘 可以给矩阵加括号改变运算顺序 求最小的运算次数

参考代码

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
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#define LL long long
#include<algorithm>
using namespace std;
LL dp[1050][1050];
int s[1050][1050];
int n;
int trans[1050];
void set()
{
	for(int r=2;r<=n;r++)          //设置每次的步长为2-n
	{
		for(int i=1;i<=n-r+1;i++)    //n-r+1为最后一个区间的起点
		{
			int j=i+r-1;         //j为每个区间的开头
			dp[i][j]=dp[i+1][j]+trans[i]*trans[i+1]*trans[j+1];   //先把A1和后面的矩阵分开 作为预处理
			s[i][j]=i;           //预处理的分开点为i
			for(int k=i+1;k<j;k++)     //预处理和遍历k可以取到的所有情况
			{
				int ans=dp[i][k]+dp[k+1][j]+trans[i]*trans[k+1]*trans[j+1];
				if(ans<dp[i][j])      //如果k处分开后的计算量小于dp 那么dp更新 断点处更新为k
				{
					dp[i][j]=ans;
					s[i][j]=k;
				}
			}
		}
	}
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	cin>>n;
	for(int i=1;i<=n;i++)
		dp[i][i]=0;
	for(int i=1;i<=n+1;i++)
		cin>>trans[i];
	set();
	cout<<dp[1][n]<<endl;
	return 0;
}

思路

迭代过程如下:

最优三角剖分

题目要求

对于一个n个顶点的凸多边形 用n-3条对角线把他分成n-2个三角形 每个三角形规定一个权函数w（i,j,k）要求分成的所有三角形
权函数最大

参考代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//与矩阵链乘的求解方式类似
//状态转移方程为：d[i,j]=max{d(i,k)+d(k,j)+w(i,j,k)}
#include <iostream>   
using namespace std;   
const int n= 6;//凸多边形边数  
int weight[][n] = {{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0}};//凸多边形的权  
int t[n][n],s[n][n];
int Weight(int a,int b,int c)  
{  
	return weight[a][b] + weight[b][c] + weight[a][c];  
}
void MinWeightTriangulation()  
{  
	for(int i=0; i<n; i++)  
	{
		t[i][i] = 0;   
		t[i][i+1]=0;
	}
	for(int r=2; r<=n; r++) //r为当前计算的链长（子问题规模）    
	{  
		for(int i=1; i<=n-r+1; i++)//n-r+1为最后一个r链的前边界    
		{  
			int j = i+r-1;//计算前边界为r，链长为r的链的后边界    
			t[i][j] = t[i+1][j] + Weight(i-1,i,j);//将链ij划分为A(i) * ( A[i+1:j] )这里实际上就是k=i  
			s[i][j] = i;  
			for(int k=i+1; k<j; k++)  
			{  
				//将链ij划分为( A[i:k] )* (A[k+1:j])     
				int u = t[i][k] + t[k+1][j] + Weight(i-1,k,j);  
				if(u<t[i][j])  
				{  
					t[i][j] = u;  
					s[i][j] = k;  
				}  
			}  
		}  
	}   
}  
void Traceback(int i,int j)  
{  
	if(i==j) return;  
	Traceback(i,s[i][j]);  
	Traceback(s[i][j]+1,j);  
	cout<<"三角剖分顶点：V"<<i-1<<",V"<<j<<",V"<<s[i][j]<<endl;  
}  
int main()  
{  
	cout<<"此多边形的最优三角剖分值为：";
	MinWeightTriangulation();
	cout<<t[1][n-1]<<endl;
	cout<<"最优三角剖分结构为："<<endl;
	Traceback(1,5); //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置  
	return 0;  
}

经典DP问题

LIS

本博客中均给出了n^2和nlogn复杂度的两种算法
转跳博客链接

LCS

状态转移方程为：
若该位置匹配dp[i][j]=dp[i-1][j-1]+1
若该位置不匹配dp[i][j]=max(dp[i-1][j],dp[i][j-1])
详见此题

连续和最大子序列问题

本题有经典的HDU 1003和HDU 1231
HDU-1003转跳链接

HDU 1231仅在1003的基础上略做修改

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

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
31
32
33
34
35
36
37
38
39
#include<iostream>
using namespace std;
int a[10050];
//状态转移方程：max=max>0?max:a[i]  若前i项和小于0 那么第i+1项不能加上sum
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		int begin=0,end=0,po=0;
		int max=a[0],sum=a[0];
		for(int i=1;i<n;i++)
		{
			if(sum<0)
			{
				sum=a[i];
				po=i;
			}
			else
				sum+=a[i];
			if(sum>max)
			{
				begin=po;
				end=i;
				max=sum;
			}
		}
		if(max<0)
			cout<<"0"<<" "<<a[0]<<" "<<a[n-1]<<endl;
		else
			cout<<max<<" "<<a[begin]<<" "<<a[end]<<endl;    //区别仅在于一个输出起始和终止位置
	}                                                     //另一个需要输出起始终止位置的值
	return 0;
}

HDU 1257

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码–dp（LIS）

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
31
32
33
34
35
36
37
#include<iostream>
#include<cstring>
using namespace std;
int num[30050];
int ans[30050];
int main()
{
    /*freopen("input.txt","r",stdin);*/
	int n;
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
			cin>>num[i];
		int len,low,high,mid;
		memset(ans,0,sizeof(ans));
		ans[1]=num[1];
		len=1;
		for(int i=2;i<=n;i++)
		{
			low=1;
			high=len;
			while(low<=high)
			{
				mid=(low+high)/2;
				if(ans[mid]<num[i])
					low=mid+1;
				else
					high=mid-1;
			}
			ans[low]=num[i];
			if(low>len)
				len++;
		}
		cout<<len<<endl;
	}
	return 0;
}

参考AC代码–贪心

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
31
32
33
34
#include<iostream>
using namespace std;
int temp[30050];
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(cin>>n)
	{
		int h,k=0;
		int flag;
		cin>>h;
		temp[0]=h;
		k++;
		for(int i=2;i<=n;i++)
		{
			cin>>h;
			flag=false;
			for(int j=0;j<k;j++)   //若第一个系统不满足 就判断第二个系统 以此类推
			{
				if(h<temp[j])     //只要满足递减 那么temp的值会更新 进行后续判断
				{
					temp[j]=h;
					flag=true;
					break;
				}
			}
			if(!flag)       //若没有一个temp可以满足递减 那么就要增加新的系统
				temp[k++]=h;    //temp数组用来存储每个新的系统
		}
		cout<<k<<endl;
	}
	return 0;
}

思路

贪心的思路较好理解 相当于判断每个系统最多能走多远 若新的高度所有系统都不满足 那么增加新的系统
dp的思路实际就是求数组的LIS长度 那么为什么可以用LIS长度呢 换句话说 为什么LIS长度就是题目的答案呢
以17 16 15 16 13 12 14 15为例
原因有如下三点：
（1）例中的LIS长度为2 第一个满足LIS=2的是数字15 16 那么后面的所有数字中不可能出现LIS=3的连续递增子序列 最多只会有2个 例如12 14
（2）后面的LIS=2的子序列肯定越来越小 例如第一个为15 16 那么后面的可能为13 14，接着比如是10 12，否则LIS就不等于2 会等于4或更多
（3）那么LIS=2的2个数字中 肯定有一个会被15的系统解决 一个被16的系统解决 所以问题得到解决 LIS就是题目答案

UVA 1471

题目要求

给一个长度为n的序列 你的任务是删除一个连续子序列 使得剩下的序列中有一个长度最大的连续递增子序列 例如，将序列｛5，3，4，9，2，8，6，7，1｝中的
｛9，2，8｝删除 得到的序列｛5，3，4，6，7，1｝中包含一个长度为4的连续递增子序列｛3，4，6，7｝ 序列每个数均不超过10^9的正整数

参考AC代码

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
31
32
33
34
35
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 2e5+5;
int f[maxn],g[maxn];//f:以第i个元素开头的最长L序列长度 g：以第i个元素结尾的最长L序列长度
int a[maxn];
int v[maxn];       //存放每个g(i)对应的最小的A[j]
const int INF = 0x3f3f3f3f;
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int Z; 
	cin>>Z;
	while(Z--)
	{
		int n; scanf("%d",&n);
		for(int i = 0; i < n; i++) scanf("%d",a+i);
		g[0] = 1;
		for(int i = 1; i < n; i++)
			g[i] = 1 + (a[i] > a[i-1] ? g[i-1] : 0);  //计算g[i]
		f[n-1] = 1;
		for(int i = n-1; i--; )
			f[i] = 1 + (a[i] < a[i+1] ? f[i+1] : 0);  //计算f[i]
		int ans = 0;
		for(int i = 0; i < n; i++)
		{
			v[1+i] = INF;
			int k = lower_bound(v+1,v+1+i,a[i])-(v+1);   //k实际为v中的索引 即对应的g[i]
			ans = max(ans,k+f[i]);            //g[i]+f[i] 取最大值
			v[g[i]] = min(v[g[i]],a[i]);      //更新v数组 确保存放的是最小值
		}                                    //在g[i]相同的情况下 数字越小 约容易和后面的数字拼揍
		printf("%d\n",ans);
	}
	return 0;
}

思路

算法入门经典（二）P242

最大子矩阵问题

HDU 1506

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给出一个直方图 每个直方图的底长为1 给出n个直方图的高度 求直方图中的最大矩形面积

参考AC代码

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
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#define LL long long
#define maxn 100050
using namespace std;
LL a[maxn];
LL l[maxn],r[maxn];
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(cin>>n)
	{
		if(n==0)
			break;
		for(int i=1;i<=n;i++)
			scanf("%I64d",&a[i]);
		l[1]=1,r[n]=n;
		for(int i=2;i<=n;i++)   //求每个点左边连续比该点大的最左边的下标，保存在l数组里
		{                       //注意保存的是下标
			int t=i;            //因为保存了l中的元素 所以可以实现跳着走
			while(t>1&&a[t-1]>=a[i])   //注意是while不是if 因为求的不是连续上升子序列
				t=l[t-1];              //只要比要比较的元素大就可以了
			l[i]=t;
		}
		for(int i=n-1;i>=1;i--)   //求每个点右边连续比该点大的最右边的下标，保存在r数组里
		{                         //注意保存的是下标
			int t=i;              //因为保存了r中的元素 所以可以实现跳着走
			while(t<n&&a[t+1]>=a[i])
				t=r[t+1];
			r[i]=t;
		}
		LL Max=0;
		for(int i=1;i<=n;i++)    //遍历每个点 右边-左边+1就是最大区间长度 ×高度就是面积
		{
			if((r[i]-l[i]+1)*a[i]>Max)   //遍历比较出最大值
				Max=(r[i]-l[i]+1)*a[i];
		}
		printf("%I64d\n",Max);
	}
	return 0;
}

HDU 1505

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

求全是F的矩形的最大面积
在上一题的基础上由一维变成二维 做法类似
在二维数组里算出连续是F的高度 每一行用上题一样的算法求解 最后把每行求得的最大值再求最大值就是答案

参考AC代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
char map[1050][1050];
int a[1005][1005],l[1005],r[1005];
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>map[i][j];
		for(int i=1;i<=m;i++)        //如果该位置是R那么置0 否则每一列迭代算出高度
		{
			for(int j=1;j<=n;j++)
			{
				if(map[j][i]=='F')
					a[j][i]=a[j-1][i]+1;
			}
		}
		int ans=-1;
		for(int i=1;i<=n;i++)     //对每一行使用HDU-1506求最大子矩阵的方法
		{
			l[1]=1,r[m]=m;
			for(int j=2;j<=m;j++)
			{
				int t=j;
				if(a[i][j]==0)
					continue;
				while (t>1&&a[i][t-1]>=a[i][j])
					t=l[t-1];
				l[j]=t;
			}
			for(int j=m-1;j>=1;j--)
			{
				int t=j;
				if(a[i][j]==0)
					continue;
				while(t<m&&a[i][t+1]>=a[i][j])
					t=r[t+1];
				r[j]=t;
			}
			for(int j=1;j<=m;j++)     //a存放的是高度 r-l+1算的是直方图的某一行能延伸的最大长度
				if((r[j]-l[j]+1)*a[i][j]>ans)
					ans=(r[j]-l[j]+1)*a[i][j];
		}                           //乘积就是矩形的面积 算出最大值
		cout<<(ans*3)<<endl;
	}
	return 0;
}
//例一迭代出的结果a为：
//0 1 1 1 1 1
//1 2 2 2 2 2
//0 0 0 3 3 3
//1 1 1 4 4 4   由于上一行的3个0导致断开 所以下行的三个1能延伸的长度均为6 因为1的高度比4的高度小
//2 2 2 5 5 5   2同理 能延伸的长度的为6 由于2的长度小于5 所以5能延伸的长度为3 3*5=15 即为答案

HDU 2870

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

给出一个矩阵 wxyz分别可以换成abc中的某一个二个或者全部 求更新后的矩阵里 字母相同的最大矩阵面积
本题相当于再在上题的基础上增加了abc三个状态 因为最后肯定是转换成全为abc状态中的某一个 所以在上一题
求每一行最大值的基础上再多算上三个状态即可

参考AC代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstring>
using namespace std;
char map[1050][1050];
char str[8]={'a','b','c','w','x','y','z'};
int num[1050][1050][3];
//num[i][j][t]表示i行j列的元素全为a，b，c中的某一个的高度（类似与直方图）
int change[7][3]={{1,0,0},{0,1,0},{0,0,1},{1,1,0},{0,1,1},{1,0,1},{1,1,1}};
//分别表示a本身b本身c本身和wxyz分别对应可以转换abc的状态 三个数字分别表示abc三种状态
int l[1050],r[1050];
int m,n;
int slove(int i)  //每一行的基础上再加三个状态
{
	int max=-1;
	for(int k=0;k<3;k++)
	{
		l[1]=1,r[m]=m;
		for(int j=2;j<=m;j++)
		{
			int t=j;
			while(t>1&&num[i][j][k]<=num[i][t-1][k])
				t=l[t-1];
			l[j]=t;
		}
		for(int j=m-1;j>=1;j--)
		{
			int t=j;
			while (t<m&&num[i][j][k]<=num[i][t+1][k])
				t=r[t+1];
			r[j]=t;
		}
		for(int j=1;j<=m;j++)
			if((r[j]-l[j]+1)*num[i][j][k]>max)
				max=(r[j]-l[j]+1)*num[i][j][k];
	}
	return max;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(cin>>n>>m)
	{
		int ans=-1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				cin>>map[i][j];
		memset(num,0,sizeof(num));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				for(int k=0;k<7;k++)   //k代表6个数字中等于哪一个
				{
					if(map[i][j]==str[k])
					{
						for(int t=0;t<3;t++)   //t表示该数字可以转换为abc中的哪一个
						{
							if(change[k][t]==1)  //如果可以转换 那么高度+1
								num[i][j][t]=num[i-1][j][t]+1;
							else
								num[i][j][t]=0;  //否则高度置0
						}
						break;
					}
				}
			}
			int temp=slove(i);   //每一行带入solve计算
			if(temp>ans)
				ans=temp;
		}
		cout<<ans<<endl;
	}
	return 0;
}

本文标题:dp基础专题五

文章作者:Hippopmonkey

发布时间:2017-02-10, 21:57:44

最后更新:2017-03-05, 18:33:29

原始链接:http://xuboming8.github.io/2017/02/10/dp专题二/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. dp专题五
    1. 1.1. 最优矩阵链乘问题
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考代码
      3. 1.1.3. 思路
    2. 1.2. 最优三角剖分
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考代码
    3. 1.3. 经典DP问题
      1. 1.3.1. LIS
      2. 1.3.2. LCS
      3. 1.3.3. 连续和最大子序列问题
      4. 1.3.4. 参考AC代码
    4. 1.4. HDU 1257
      1. 1.4.1. 参考AC代码–dp（LIS）
      2. 1.4.2. 参考AC代码–贪心
      3. 1.4.3. 思路
    5. 1.5. UVA 1471
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. 最大子矩阵问题
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 题目要求
      4. 1.6.4. 参考AC代码
      5. 1.6.5. 题目要求
      6. 1.6.6. 参考AC代码
|