• 【动态规划】区间动态规划

    知识点

    一 . 区间DP

    区间DP属于线性DP的一种，以区间长度作为DP的阶段，以区间的左右端点作为状态的维度。一个状态通常由被它包含且比它更小的区间状态转移而来。阶段（长度）、状态（左右端点）、决策三者按照由外到内的顺序构成三层循环。 

    一般解法

    dp[i][j]表示区间i到j上的最优解
    从小到大求出所有区间的最优解，具体通过从小到大遍历区间长度和左端点实现
    这是区间dp的最基本的特征或者套路。

    比较特殊的还有一种操作方法：

    用k将区间i到j分割为两个部分，通过这两个部分求最优解。这其实也是划分子问题的常用方法。
     

    一 . 环形区间合并问题 

    例题： 洛谷 P1880 [NOI1995] 石子合并 

    题目描述

    在一个圆形操场的四周摆放 N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

    试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。

    输入格式

    数据的第 1 行是正整数 N，表示有 N 堆石子。

    第 2 行有 N 个整数，第 i 个整数 a_i表示第 i 堆石子的个数。

    输出格式

    输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

    输入输出样例

    输入 #1

    4
4 5 9 4

    输出 #1

    43
54

    说明/提示

    1\leqslant N\leqslant 100，0\leqslant a_i\leqslant 20。

    思路：因为在一个圆形操场上，所以可以出现每一个数据都可以成为开头的情况，所以需要将环形数据展开形成一条链。

    因此，输入样例可以变成一条链，红框表示环转换成链前，可能出现的大区间情况，即哪个点作为起点。

    设dp[l][r]为石子合并的总方法，下标 l 表示从节点 l 进行合并，下标 r 表示从 l 开始数 i 堆进行合并操作，代码中循环下标 j 表示 l 到 r 存在 j 种合并方式。 

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. int n;
    7. const int INF=0x3f3f3f3f;
    8. int dp_max[205][205],dp_min[205][205],a[205],sum[205];
    9. inline int read()
    10. {
    11. 	int x=0,f=1;
    12. 	char c=getchar();
    13. 	while(c<'0'||c>'9')
    14. 	{
    15. 		if(c=='-') f=-1;
    16. 		c=getchar();
    17. 	}
    18. 	while(c>='0'&&c<='9')
    19. 	{
    20. 		x=(x<<3)+(x<<1)+(c^48);
    21. 		c=getchar();
    22. 	}
    23. 	return x*f;
    24. }
    25.  
    26. int main()
    27. {
    28. 	n=read();
    29. 	for(int i=1;i<=n;++i)
    30. 	{
    31. 		a[i]=read();
    32. 		a[i+n]=a[i]; //环变成链
    33. 	}
    34. 	int len=(n<<1)-1;
    35. 	for(int i=1;i<=len;++i)
    36. 	{
    37. 		sum[i]=sum[i-1]+a[i]; //前缀和统计
    38. 	}
    39. 	memset(dp_min,INF,sizeof(dp_min));
    40. 	for(int i=1;i<=(n<<1);++i)
    41. 	{
    42. 		dp_min[i][i]=0; //记得初始化
    43. 	}
    44.  
    45. 	for(int i=1;i<=n;++i) //有几堆石子需要合并
    46. 	{
    47. 		for(int l=1;l<=len-i+1;++l) //区间的左端点
    48. 		{
    49. 			int r=l+i-1; //区间的右端点
    50. 			for(int j=l;j//区间内部的节点
    51. 			{
    52. 			dp_max[l][r]=max(dp_max[l][r],dp_max[l][j]+dp_max[j+1][r]+sum[r]-sum[l-1]);
    53. 			dp_min[l][r]=min(dp_min[l][r],dp_min[l][j]+dp_min[j+1][r]+sum[r]-sum[l-1]);
    54. 			}
    55. 		}
    56. 	}
    57. 	int max_res=0,min_res=INF;
    58. 	for(int i=1;i<=n;++i)
    59. 	{
    60. 		max_res=max(max_res,dp_max[i][i+n-1]);
    61. 		min_res=min(min_res,dp_min[i][i+n-1]);
    62. 	}
    63. 	printf("%d\n%d",min_res,max_res);	
    64. 	return 0;
    65. }

    相关练习

    1 . 洛谷 P1063 [NOIP2006 提高组] 能量项链

    思路：

    如果该题不成环，就是矩阵乘法的模板题。因为“第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记”说明成环，需要将环转换成链，再进行矩阵乘法。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define ll long long
    6. using namespace std;
    7. int n;
    8. const int maxn=205;
    9. int a[maxn];
    10. ll int dp[maxn][maxn];
    11. inline int read()
    12. {
    13. 	int x=0,f=1;
    14. 	char c=getchar();
    15. 	while(c<'0'||c>'9')
    16. 	{
    17. 		if(c=='-') f=-1;
    18. 		c=getchar();
    19. 	}
    20. 	while(c>='0'&&c<='9')
    21. 	{
    22. 		x=(x<<1)+(x<<3)+(c^48);
    23. 		c=getchar();
    24. 	}
    25. 	return x*f;
    26. }
    27.  
    28. int main()
    29. {
    30. 	n=read();
    31. 	for(int i=1;i<=n;++i)
    32. 	{
    33. 		a[i]=read();
    34. 		a[n+i]=a[i]; //转环为链的方法
    35. 	}
    36. 	
    37. 	int len=(n<<1)-1;
    38. 	for(int i=1;i<=len;++i)
    39. 	{
    40. 		dp[i][i]=0;
    41. 	}
    42. 	
    43. 	
    44. 	for(int i=2;i<=n;++i) //枚举几颗珠子要合并
    45. 	{
    46. 		for(int l=1;l<=len-i+1;++l) //从哪个节点开始合并
    47. 		{
    48. 			int r=l+i-1; //合并结束的范围
    49. 			for(int k=l;k
    50. 			{
    51. 				dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l]*a[k+1]*a[r+1]);
    52.                 //对于从节点l开始合并，需要合并的是在l节点后一个和两个的节点
    53. 			}
    54. 		}
    55. 	}
    56. 		
    57. 	ll int Max=0;	
    58. 	for(int i=1;i<=n;++i)
    59. 	{
    60. 		Max=max(Max,dp[i][i+n-1]); //记录最大的能量
    61. 	}
    62. 	printf("%d",Max);
    63. 	return 0;
    64. }

    二 . 线性区间合并问题

    例题：洛谷 P3146 [USACO16OPEN]248 G

    思路：这道题需要注意的是：只有在相邻的两个数相同的时候才能进行合并，并且合并后的数值并非加倍而是+1。另外，在当前数据无法进行合并的时候，要初始化当前dp[i][i]数组为自己本身。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. int n;
    7. const int maxn=255;
    8. int a[maxn],dp[maxn][maxn];
    9. inline int read()
    10. {
    11. 	int x=0,f=1;
    12. 	char c=getchar();
    13. 	while(c<'0'||c>'9')
    14. 	{
    15. 		if(c=='-') f=-1;
    16. 		c=getchar();
    17. 	}
    18. 	while(c>='0'&&c<='9')
    19. 	{
    20. 		x=(x<<3)+(x<<1)+(c^48);
    21. 		c=getchar();
    22. 	}
    23. 	return x*f;
    24. }
    25.  
    26. int main()
    27. {
    28. 	n=read();
    29. 	for(int i=1;i<=n;++i)
    30. 	{
    31. 		a[i]=read();
    32. 		dp[i][i]=a[i]; //记得未合并前是自身数据
    33. 	}
    34. 	int Max=0;
    35. 	for(int i=2;i<=n;++i)
    36. 	{
    37. 		for(int l=1;l<=n-i+1;++l)
    38. 		{
    39. 			int r=l+i-1;
    40. 			for(int k=l;k
    41. 			{
    42. 				if(dp[l][k] == dp [k+1][r] && dp[l][k]!=0 && dp[k+1][r]!=0) 
    43.                 //需要保证左右两数相等且不超出总数范围
    44. 				dp[l][r]=max(dp[l][r],dp[l][k]+1);
    45. 				Max=max(Max,dp[l][r]); //记录数据
    46. 			}
    47. 		}
    48. 	}
    49. 	printf("%d",Max);
    50. 	return 0;
    51. }

    三 . 回文串区间处理问题 

    例题：洛谷 P2890 [USACO07OPEN]Cheapest Palindrome G

    思路：对于字符串中的每一个位置而言，每个位置可以选择删除还是在此位置增加字符或者原来在该位置的字符不变。

    设dp[i][j]为进行转换后的成本，下标 i 表示从前向后查找的字母s[i]，下标 j 表示从后向前查找的字母s[j]，因为要使最后的字符串是一个回文串并且使得得到该回文串的成本最小，对于一个回文字符串来说，要想保持回文性，有两种方法：在右侧添加一个同样的字符，或者将左侧字符删去。可以看出，对于一个字符而言，插入和删除的权值没有区别，可以只存最小值。所以增加或删除字母s[i]/s[j]与操作前比较，取最小值。

    但是需要注意一个特判条件：当 r == l+1时，会调用dp[i+1][i]，所以需要在初始化的时候处理为0。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define ll long long
    6. using namespace std;
    7. int n,m;
    8. const int maxn=1e4+5,INF=0x3f3f3f3f;
    9. char s[maxn];
    10. struct node{
    11. 	char c;
    12. 	int add,de;
    13. }made[maxn<<1];
    14. ll int dp[2005][2005];
    15. inline int read()
    16. {
    17. 	int x=0,f=1;
    18. 	char c=getchar();
    19. 	while(c<'0'||c>'9')
    20. 	{
    21. 		if(c=='-') f=-1;
    22. 		c=getchar();
    23. 	}
    24. 	while(c>='0'&&c<='9')
    25. 	{
    26. 		x=(x<<3)+(x<<1)+(c^48);
    27. 		c=getchar();
    28. 	}
    29. 	return x*f;
    30. }
    31.  
    32. int main()
    33. {
    34. 	memset(dp,INF,sizeof(dp));
    35. 	n=read(); m=read();
    36. 	for(int i=1;i<=m;++i)
    37. 	{
    38. 		cin>>s[i];
    39. 	}
    40. 	for(int i=1;i<=n;++i)
    41. 	{
    42. 		cin>>made[i].c;
    43. 		int num=made[i].c-'a'+1; 
    44.             //将字符转换成数字，当字符串的某一位是该字符，增加/删去的值就可直接查找
    45. 		made[num].add=read(); 
    46. 		made[num].de=read();
    47. 	}
    48. 	
    49. 	for(int i=1;i<=n;++i)
    50. 	{
    51. 		dp[i][i]=0; //自身本来就可以构成一个回文串
    52. 		dp[i+1][i]=0; //特判
    53. 	}
    54. 	
    55. 	for(int l=1;l<=m;++l)
    56. 	{
    57. 		for(int i=1;i<=m-l+1;++i)
    58. 		{
    59. 			int j=l+i-1;
    60. 			if(i == j) dp[i][j]=0;
    61. 			else if(s[i]==s[j])
    62. 			{
    63. 			dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
    64.                  //当前位置的字母相同，直接把上一个位置的值移下来
    65. 			}
    66. 			else 
    67. 			{
    68. 				int num1=s[i]-'a'+1,num2=s[j]-'a'+1;
    69. 				dp[i][j]=min(dp[i][j],dp[i+1][j]+min(made[num1].add,made[num1].de));
    70. 				dp[i][j]=min(dp[i][j],dp[i][j-1]+min(made[num2].add,made[num2].de));
    71.                 //分别处理左右节点，对于对于s[i]/s[j]这个字母，是否增加/删除
    72. 			}	
    73. 		}
    74. 	}
    75. 	printf("%lld",dp[1][m]);
    76. 	return 0;
    77. }

    相关练习：

    1 . CF245H Queries for Number of Palindromes

     思路：先预处理字符串每种情况下有多少个回文串，从小区间到大区间进行枚举，再进行查询。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7. int q,l,r;
    8. const int maxn=5555;
    9. int dp[maxn][maxn],res[maxn][maxn];
    10. string s;
    11. inline int read()
    12. {
    13. 	int x=0,f=1;
    14. 	char c=getchar();
    15. 	while(c<'0'||c>'9')
    16. 	{
    17. 		if(c=='-') f=-1;
    18. 		c=getchar();
    19. 	}
    20. 	while(c>='0'&&c<='9')
    21. 	{
    22. 		x=(x<<3)+(x<<1)+(c^48);
    23. 		c=getchar();
    24. 	}
    25. 	return x*f;
    26. }
    27.  
    28. int main()
    29. {
    30. 	cin>>s;
    31. 	int n=s.length();
    32. 	for(int i=0;i
    33. 	{
    34. 		dp[i][i]=res[i][i]=1;
    35. 	}
    36. 			
    37. 	for(int le=1;le
    38. 	{
    39. 		for(int i=0;i
    40. 		{
    41. 			int j=le+i;
    42. 			if(s[i] == s[j]) 
    43. 			{
    44. 				if(le!=1) res[i][j]=res[i+1][j-1];
    45.             //如果长度不为1，且所指位置两个字符相同，那么当前位置的回文串总数传递到下一个阶段
    46. 				else res[i][j]=1;
    47. 			}
    48. 			else res[i][j]=0;
    49. 		}
    50. 	}
    51. 	
    52. 	for(int le=1;le
    53. 	{
    54. 		for(int i=0;i
    55. 		{
    56. 			int j=le+i;
    57. 			dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+res[i][j];     
    58.  //状态转移方程：
    59.    //当前位置的回文串总数与左端点的字符向右找一位、右端点的字符向左找一位和预处理当前位置的值	
    60. 		}
    61. 	}
    62. 	
    63. 	q=read();
    64. 	while(q--)
    65. 	{
    66. 		l=read(); r=read();
    67. 		l=l-1; r=r-1; //字符串的下标从0开始
    68. 		printf("%d\n",dp[l][r]);
    69. 	}	
    70. 	return 0;
    71. }

  • 相关阅读:
    如何将变量用作typescript的类型注解
    智能指针篇
    Ansible自动化部署工具-role模式安装filebeat实际案例分析
    23年下半年软考中级软件设计师备考攻略（含报名时间）
    DBPack 限流熔断功能发布说明
    Day15--加入购物车-初始化vuex
    线程间有哪些资源是不可以共享的？
    LeetCode 1624. 两个相同字符之间的最长子字符串
    华为数通方向HCIP-DataCom H12-821题库(多选题：41-60)
    Java-多线程的使用
  • 原文地址：https://blog.csdn.net/gzkeylucky/article/details/126633596