区间dp
admin
|
|
366
|
算法知识总结

1991 字
|
22 分钟

石子合并

题目描述：

设有 NN 堆石子排成一排，其编号为 1，2，3，…，N1，2，3，…，N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 NN 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 44 堆石子分别为 1 3 5 2， 我们可以先合并 1、21、2 堆，代价为 44，得到 4 5 2， 又合并 1，21，2 堆，代价为 99，得到 9 2 ，再合并得到 1111，总代价为 4+9+11=244+9+11=24；

如果第二步是先合并 2，32，3 堆，则代价为 77，得到 4 7，最后一次合并代价为 1111，总代价为 4+7+11=224+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价

思路：

很显然贪心不可取，因为合并的只能是相邻的石子，而不是取任意的去合并，这时贪心就贪不成

其实这个题是区间dp

核心:

最后一次合并一定是左边连续的一部分和右边连续的一部分合并

状态：
状态方程：
dp[i][j] = 0//i = j
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1])//i < j
  //如果你是第一次学这个区间dp的话，肯定会一脸懵，这是什么，那是什么
  //其实因为dp[i][j]表示的是i到j合并成一堆的方案数，是由两部分组成的，我们要让他最小，就考虑怎样分成两部分，让他们的和最小，也就是去枚举分割点 k ，所以区间[i,j]就分成[i,k]和[k + 1，j]两部分，也就是我们只需要求他们俩的和再加上这次合并的代价，也就是区间[i,j]的和，这里就得用到前缀和，所以就是加上sum[j] - sum[i - 1]，最后问最小代价，就对每次枚举k的结果取最小值即可，而最终答案就是dp[1] [n]

贴份ac代码

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int sum[MAX], dp[MAX][MAX];
int n, x;

int main(){
    io;
    cin>>n;
    mem(dp, inf);//初始化为无穷大
    for(int i = 1; i <= n; ++i){
        cin>>x;
        sum[i] = sum[i - 1] + x;//求前缀和
        dp[i][i] = 0;//初始化,不能将i自身进行合并，所以是0
    }
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1;
            if(j > n)break;//数组越界，故跳出
            for(int k = i; k < j; ++k){
                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}

很显然，这个区间dp就他喵是个大暴力？！orz

时间复杂度：

这暴力也太暴力了叭，想出这算法的人绝对是个大聪明orz

为了过防止某些毒瘤出题人卡我们，我们得学习一下四边形不等式优化

其优化效果十分给力，但数学味道比较浓重(#ﾟДﾟ)

我这里来简单介绍一下下我的理解

首先，我们再次拿出我们的状态转移方程：

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)

m(i, j)表示区间i到j内的某个最优解，w(i, j)表示转移时需要付出的额外代价

先来看一下什么是区间包含的单调性和四边形不等式

  • 区间包含的单调性指的是，对于一个区间，其中有四个点满足

i <= i' < j <= j'，则有w[i', j] <= w[i, j']（简单来说就是小区间的w和小于大区间的w和）

  • 四边形不等式指的是，如果对于i <= i' < j <= j' 有w[i, j] + w[i', j'] <= w[i, j'] + w[i', j] ，则我们称函数w满足四边形不等式，简单来说就是两个交错的区间的w的和不超过小区间和大区间的w的和）

下面给出两个定理：

  • 如果上述函数w同时满足区间包含的单调性和四边形不等式，则函数m也满足四变形不等式
  • 定义s(i, j)表示m(i, j)取得最优值对应的下标。如果m(i, j)满足四变形不等式，则s(i, j)单调，即s(i, j) < s(i, j + 1) < s(i + 1，j + 1)，也就是s(i, j – 1) < s(i, j) < s(i + 1, j)

所以状态转移方程可以写为：

m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(s(i,j-1)≤k≤s(i+1,j))

再贴一发代码

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int sum[MAX], dp[MAX][MAX], s[MAX][MAX];
int n, x;

int main(){
    io;
    cin>>n;
    mem(dp, inf);
    for(int i = 1; i <= n; ++i){
        cin>>x;
        sum[i] = sum[i - 1] + x;
        dp[i][i] = 0;//初始化
        s[i][i] = i;//初始化
    }
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1;
            if(j > n)break;
          //枚举k，特别要注意这里k是小于等于
            for(int k = s[i][j - 1]; k <= s[i + 1][j]; ++k){
              //找到小的值就更新，切记要更新s[i][j]的值
                if(dp[i][j] > dp[i][k] + dp[k + 1][j]){
                    dp[i][j] = dp[i][k] + dp[k + 1][j];
                    s[i][j] = k;
                }
            }
            dp[i][j] += sum[j] - sum[i - 1];
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}

P1880 [NOI1995] 石子合并

这个就是在环的基础上去进行区间dp，相比于单个区间dp，这个就相当于是对n个长度为n的区间进行区间dp，求最小和最大值，这个做法就是开二倍的数组，然后在这个二倍的数组的基础上去进行dp，第一层循环的长度是n，这个不会变，因为所需区间长度为n，但第二层循环的结束位置是n * 2 – 1，也就是在最后，因为我们第二层循环枚举的是起点，同样的，第三层循环结束也是在n * 2 – 1，因为第三层循环循环的是结束位置

最后我们需要对1到n的dp[i] [i + n – 1]去循环一遍最大和最小值

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m;
int dp[MAX][MAX], s[MAX][MAX], sum[MAX], tr[MAX], dp2[MAX][MAX];

int main(){
    cin>>n;
    mem(dp, inf);//求最小值，所以赋初值为无穷大
    mem(dp2, -1);//求最小值，所以赋初值为-1
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
        tr[n + i] = tr[i];//将前n个数复制到后面去
    }
    for(int i = 1; i <= 2 * n; ++i){
        sum[i] = sum[i - 1] + tr[i];//求前缀和
        dp[i][i] = 0;//赋初值
        dp2[i][i] = 0;//赋初值
    }
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i <= n * 2 - 1; ++i){
          //注意循环结束条件
            int j = i + len - 1;
            if(j > n * 2 - 1)break;//判出界
            for(int k = i; k < j; ++k){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
                dp2[i][j] = max(dp2[i][j], dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }
    int minx = inf, maxn = -1e9;
  //循环找最大和最小值
    for(int i = 1; i <= n; ++i){
        minx = min(minx, dp[i][i + n - 1]);
        maxn = max(maxn, dp2[i][i + n - 1]);
    }
    cout<<minx<<endl<<maxn<<endl;
}

同样的，我们可以对其进行四变形优化

不过对于最大值，其不满足四变形的单调规则，所以不能用四变形法则去优化，不过他的最大值可以直接取区间的端点

为什么呢？

首先可以把最后一步看成两堆石子合并，倒数第二部看成三堆石子中的两堆合并，再与第三堆合并。
那三堆中哪两堆合并呢？
(用w[i]表示第i堆重量)
前两堆:w1=2w[1]+2w[2]+w[3]w1=2w[1]+2w[2]+w[3]
后两堆:w2=w[1]+2w[2]+2w[3]w2=w[1]+2w[2]+2w[3]
所以应该将1号和3号中较大的一堆与第2堆合并，也就是把一堆合并得尽可能大，所以就有

dp2[i][j]=max(dp2[i+1][j],dp2[i][j-1])+sum[j]-sum[i-1];

再贴一份代码

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m;
int dp[MAX][MAX], s[MAX][MAX], sum[MAX], tr[MAX], dp2[MAX][MAX];

int main(){
    cin>>n;
    mem(dp, inf);
    mem(dp2, -1);
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
        tr[n + i] = tr[i];
    }
    for(int i = 1; i <= 2 * n; ++i){
        sum[i] = sum[i - 1] + tr[i];
        dp[i][i] = 0;
        dp2[i][i] = 0;
        s[i][i] = i;
    }
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i <= n * 2 - 1; ++i){
            int j = i + len - 1;
            if(j > n * 2 - 1)break;
            dp2[i][j] = max(dp2[i][j - 1], dp2[i + 1][j]) + sum[j] - sum[i - 1];
            for(int k = s[i][j - 1]; k <= s[i + 1][j]; ++k){
                if(dp[i][j] > dp[i][k] + dp[k + 1][j]){
                    dp[i][j] = dp[i][k] + dp[k + 1][j];
                    s[i][j] = k;
                }
            }
            dp[i][j] += sum[j] - sum[i - 1];
        }
    }
    int minx = inf, maxn = -1e9;
    for(int i = 1; i <= n; ++i){
        minx = min(minx, dp[i][i + n - 1]);
        maxn = max(maxn, dp2[i][i + n - 1]);
    }
    cout<<minx<<endl<<maxn<<endl;
  	return 0;
}

Running Routes

好了，终于到了我学区间dp的原因了o(︶︿︶)o

题意：

给你一个n，代表有一个n边形

再来一个二维数组tr[i] [j] 表示i 和 j 之间有木有线，1则有，0则无

问你最多能用多少条线连接两个点，点不能连重复（一个点最多和一个点相连），且tr[] []为0的两个点之间不能连线

思路：

区间dp叭,

去枚举连接的两个点，一个点可以一直固定成i，然后去枚举另一个点k

状态：

区间可以分为两种情况

状态方程：

就是去枚举位置k，然后将 i 和 k 连起来，长此以往递归下去

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 500 + 7
#define endl '\n'
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
        ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n;
int tr[MAX][MAX], dp[MAX][MAX];

int main(){
    cin>>n;
    for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)cin>>tr[i][j];
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i <= n; ++i){
            int j = i + len - 1;
            if(j > n)break;
            for(int k = i; k <= j; ++k){
                dp[i][j] = max(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + tr[i][k]);
            }
        }
    }
    cout<<dp[1][n] <<endl;
    return 0;
}

首次接触这个区间dp，还有很多不足，和例题没来得及做，我一定会回来了的(>_<)

博客内容均系原创，未经允许严禁转载！
dp
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Lemonade Trade「dp + 对数优化」

							
							

							
刷墙「区间dp」

							
							

							
AtCoder Beginner Contest 238 F – Two Exams「dp + 二维偏序」

							
							

							
leetcode 1937. 扣分后的最大得分「动态规划」「拆项」

							
							

							
AtCoder Beginner Contest 236 E – Average and Median 「二分答案 + dp」