高级数据结构与算法期末考试速成记录2
继续上一篇的高级数据结构与算法的期末速成
2.3动态规划之凸多边形最优三角剖分
问题描述:
多边形的边除了顶点没有别的交点，这就是一个简单的多边形。简单的多边形可以将平面分为三个部分：被包围在多边形内的所有点构成了多边形的内部，多边形本身构成多边形的边界，平面上其余被多边形包围的点构成了多边形的外部。
当一个简单多边形和其内部构成一个凸集时，则称该简单多边形为一个凸多边形。
用多边形顶点的逆时针序列表示凸多边形，即 P = v 0 , v 1 , … , v n − 1 P={v_0,v_1,…,v_{n-1}} P=v0,v1,…,vn−1表示具有n条边的凸多边形。
若 v i 与 v j v_i与v_j vi与vj是多边形上不相邻的2个顶点，则线段 v i v j v_iv_j vivj称为多边形的一条弦。
弦将多边形分割成2个多边形 v i , v i + 1 , … , v j {v_i,v_{i+1},…,v{j}} vi,vi+1,…,vj和 v j , v j + 1 , … v n − 1 {v_j,v_{j+1},…v_{n-1}} vj,vj+1,…vn−1。
多边形的三角剖分是将多边形分割成互不相交的三角形的**弦**的集合T.
给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。
输入描述:
首先输入一个正整数 n n n表示顶点数,之后你是弦的信息按照a b weight的格式给出
输出:
三角剖分中诸三角形上权之和为最小。
(注意:这个题没有找链接,也没找示例)
思路:
证明最优子结构就不证明了,两个弦就可以把问题分为两个子问题,最优解就是weight(i,k)+weight(k,j)+dp[i][k-1]+dp[k+1][j]这个就是和上一个矩阵连乘问题比较相似.
代码示例:
#include <bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;int weight[n+2][n+2]={0};int ans=INT_MAX;int dp[n+2][n+2];memset(dp,0,sizeof dp);for(int i=0;i<n*n-3*n;i++){int a,b,c;cin>>a>>b>>c;weight[a][b]=c;}for(int i=1;i<=n;i++)dp[i][i]=0;for(int r=2;r<=n;r++){for(int i=1;i<=n-r+1;i++){int j=i+r-1;dp[i][j]=dp[i+1][j]+weight[i-1][i]+weight[i][j];for(int k=i+1;k<i+r-1;k++){dp[i][j]=min(dp[i][j],dp[k][j]+weight[i-1][k]+weight[i][j]);}}}cout<<dp[1][n]<<endl;return 0;
}
代码不一定对(🤣🤣🤣🤣)
2.4动态规划之石子合并
问题描述:
设有 N N N堆石子排成一排,其编号为 1 , 2 , 3 , . ⋅ ⋅ , N 1,2,3,.··,N 1,2,3,.⋅⋅,N。
每堆石子有一定的质量,可以用一个整数来描述,现在要将这$ N $堆石子合并成为一堆。
每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,
合并时由于选择的顺序不同,合并的总代价也不相同。
例如有 4 堆石子分别为1 3 5 2,我们可以先合并1、2 堆,代价为 4,得到4 5 2,又合并1、2 堆,代价为9,得到9 2,再合并得到11,总代价为 4+9+11=24;
如果第二步是先合并 2、3堆,则代价为 7,得到4 7,最后一次合并代价为 11,总代价为
4 + 7 + 11 = 22。
问题是:找出一种合理的方法,使总的代价最小,输出最小代价。
输入格式:
第一行一个数 N 表示石子的堆数 N。
第二行 N 个数,表示每堆石子的质量(均不超过1000)。
输出格式:
输出一个整数,表示最小代价。
测试连接
思路分析:
最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并,之后就把整个石头堆合并是一个定值,可以使用前缀和快速得到某段区间的和.
状态表示:$f[i][j] 表示 表示 表示从i到j$这一段石子合并成一堆的方案的最小代价
则易得状态转移方程为:
y ( x ) = { min i ≤ k ≤ j − 1 { f [ i ] [ k ] + f [ k + 1 ] [ j ] + s [ j ] − s [ i − 1 ] } , i < j , 0 , i = j . y(x) = \begin{cases} \displaystyle \min_{\,i \le k \le j-1} \bigl\{\,f[i][k] \;+\; f[k+1][j] \;+\; s[j] - s[i-1] \bigr\}, & i < j, \\[1ex] 0, & i = j. \end{cases} y(x)=⎩ ⎨ ⎧i≤k≤j−1min{f[i][k]+f[k+1][j]+s[j]−s[i−1]},0,i<j,i=j.
示例代码:
#include <bits/stdc++.h>
using namespace std;const int N = 307;
int arr[N], sum[N];
int dp[N][N];
int main() {int n;cin >> n;for (int i = 1; i <= n; i ++) {cin >> arr[i];sum[i] += sum[i - 1] + arr[i];}memset(dp, 0x3f, sizeof dp);// 区间 DP 枚举套路：长度+左端点for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素个数for (int i = 1; i + len - 1 <= n; i ++) {int j = i + len - 1; // 自动得到右端点if (len == 1) {dp[i][j] = 0; // 边界初始化continue;}for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= jdp[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;
}
2.5动态规划之多边形游戏(没写)
测试链接
题目描述:
“多边形游戏"是一款单人益智游戏。 游戏开始时,给定玩家一个具有 N N N 个顶点$ N$ 条边(编号 1 → N 1\to N 1→N)的多边形,如图 1所示,其中 N= 4。 每个顶点上写有一个整数,每个边上标有一个运算符+(加号)或运算符*(乘号)。
第一步,玩家选择一条边,将它删除。
接下来在进行 N-1步,在每一步中,玩家选择一条边,把这条边以及该边连接的两个顶点用一个新的顶点代替,新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到的结果。下面是用一个例子进行游戏的全过程。
最终,游戏仅剩一个顶点,顶点上的数值就是玩家的得分,上图玩家得分为0。
请计算对于给定的 N 边形,玩家最高能获得多少分,以及第一步有哪些策略可以使玩家获得最高得分。
输入格式:
输入包含两行,第一行为整数N。
第二行用来描述多边形所有边上的符号以及所有顶点上的整数,从编号为1的边开始,边、点、边…按顺序描述。
其中描述顶点即为输入顶点上的整数,描述边即为输入边上的符号,其中加号用t表示,乘号用×表示。
输出格式:
输出包含两行,第一行输出最高分数。
在第二行,将满足得到最高分数的情况下,所有的可以在第一步删除的边的编号从小到大输出,数据之间用空格隔开。
输入样例：
4
t -7 t 4 x 2 x 5
输出样例：
33
1 2
思路分析:
这是一个标准的区间DP问题，这个题跟石子合并非常相似，只不过它是一个环形结构，所以形成一个2倍长度的链就可以很好的解决环形区间DP问题。
本题在基于“石子合并”的基础之上终于被我完完全全写出来了，“石子合并”是线性的，可用前缀和优化的一种题型，且也本题的计数方式也不同，在“石子合并”中，每次花费是将两个堆的总质量，本题中是两个堆的加或乘运算，所以不必使用前缀和，在写这个题的时候算的时间复杂度是50^5,完全没有办法求其前缀和，后来才明白，这里使用前缀和反而会有问题。
本题是一个环形数据，所以我们按照老套路直接破环成链，将链双倍，然后和石子合并一致，f[i][j]表示从i点到j点之间所有点的合并最后剩下的值，但是考虑到题目里面数据会出现负数，会出现很多负数在最后一下变成很大的正数的可能，所以我们扩充一维度的空间，同时来存储max和min，在每一次区间合并转移的时候用四个状态来转移就能确保万无一失。
状态表示：f[i][j][0]从i到j全部合后的最大值，f[i][j][1]从i到j全部合并后的最小值
f[i][j]可以使用f[i][k]和f[k+1][j]的组合四种方式转移而来（++、+-、-+、--）
通常使用两重循环来解决这个繁琐的取max和min的过程
get函数，是运算过程，f[i][k]和f[k+1][j]配上对应符号的计算
for(int a = 0; a <= 1; a ++)//(max, max) (max, min) (min, max) (min, min)for(int b = 0; b <= 1; b ++){f[i][j][0] = max(f[i][j][0], get(f[i][k][a], f[k+1][j][b], op[k+1]));f[i][j][1] = min(f[i][j][1], get(f[i][k][a], f[k+1][j][b], op[k+1]));}
代码示例:
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 55, INF = 0x3f3f3f3f;
int q[N*2], f[N*2][N*2][2];//f[i][j][0]表示从i点到第j点合并后的max, f[i][j][1]表示min
char op[N*2];
int n;int get(int a, int b, char ch){if(ch == 'x') return a * b;else return a + b;
}int main()
{cin >> n;for(int i = 1; i <= n; i ++){//这里直接处理成为一个环形，且将数值和符号分开存储cin >> op[i] >> q[i];op[i+n] = op[i]; q[i+n] = q[i];}for(int i = 1; i <= 2*n; i ++)//初始化数据for(int j = i; j <= 2*n; j ++)if(i == j) f[i][i][1] = f[i][i][0] = q[i];//当前只有自己一个点//当前没有合并，联系状态表示这里要正负极限else f[i][j][0] = -INF, f[i][j][1] = INF;for(int len = 2; len <= n; len ++)//枚举当前区间合并的长度for(int i = 1; i+len-1 <= 2*n; i ++)//枚举左端点{int j = i+len-1;//计算当前右端点for(int k = i; k < j; k ++)//枚举子区间来更新自己{for(int a = 0; a <= 1; a ++)//(max, max) (max, min) (min, max) (min, min)for(int b = 0; b <= 1; b ++){f[i][j][0] = max(f[i][j][0], get(f[i][k][a], f[k+1][j][b], op[k+1]));f[i][j][1] = min(f[i][j][1], get(f[i][k][a], f[k+1][j][b], op[k+1]));}}}int maxn = -INF;int rnt[200], idx = 0;for(int i = 1; i <= n; i ++){int t = f[i][i+n-1][0];//得到这一组解if(t > maxn){idx = 0; rnt[idx ++] = i; maxn = t;}else if(t == maxn) rnt[idx ++] = i;}cout << maxn << endl;for(int i = 0; i < idx; i ++) cout << rnt[i] << ' ';return 0;
}
2.6动态规划之区间和最大问题
题目链接
题目描述:
给定一个包含K个整数的序列 N 1 , N 2 , ⋅ ⋅ ⋅ , N K {N_1,N_2,···,N_K} N1,N2,⋅⋅⋅,NK。
连续子序列定义为 N i , N i + 1 , ⋅ … . , N j {N_i,N_{i+1},·….,N_j} Ni,Ni+1,⋅….,Nj,其中1≤i≤j≤K。
最大子序列是指序列内各元素之和最大的连续子序列。
例如,给定序列 − 2 , 11 , − 4 , 13 , − 5 , − 2 {-2,11,-4,13,-5,-2} −2,11,−4,13,−5,−2,它的最大子序列为 11 , 一 4 , 13 {11,一4,13} 11,一4,13,其各元素之和为 20。
现在你需要求出最大子序列的各元素之和,并且输出最大子序列的第一个元素和最后一个元素的值。
输入格式:
第一行包含一个整数 K K K。第二行包含$ K 个整数。输出格式 : 输出一行三个整数 , 分别表示最大子序列的各元素之和以及最大子序列的第一个元素和最后一个元素的值。如果答案不唯一 , 则选择更小的解 , 如果仍不唯一 , 则选择 个整数。 输出格式: 输出一行三个整数,分别表示最大子序列的各元素之和以及最大子序列的第一个元素和最后一个元素的值。 如果答案不唯一,则选择更小的解,如果仍不唯一,则选择 个整数。输出格式:输出一行三个整数,分别表示最大子序列的各元素之和以及最大子序列的第一个元素和最后一个元素的值。如果答案不唯一,则选择更小的解,如果仍不唯一,则选择j$更小的解。注意,我们规定,如果所有 K个数字均为负数,则其最大和定义为0,并且应该输出整个序列的第一个数字和最后一个数字。
思路:
最大子段和肯定是以原来数组中某个数字为结尾,那么就枚举结尾就行了,这个数字要么单独自己,不和前面的字段和融合,要么和前面的子段和融合.之后还需要维护最大子段和的左右区间的端点.如果发现前面的子段和小于0那么肯定这个子段和单独自己,所以左端点是自己.如果这个子段和大于最大的子端和,那么右端点更新为以他结尾.如果最大子端和小于0,就按照题目去做就行了.
#include <iostream>using namespace std;const int N = 1000010, INF = 0x3f3f3f3f;int a[N], n;
int dp[N]; //以i结尾的最大子序列int main()
{cin >> n;for (int i = 1; i <= n; i++) scanf("%d", &a[i]);int res = -INF, l = 1, r = 1, ltmp = 1;//ltmp子段的临时的左端点for (int i = 1; i <= n; i ++){dp[i] = max(dp[i - 1] + a[i], a[i]);//要么自己,要么和前面的结合if (dp[i - 1] < 0)//如果前面的字段和小于0,那么肯定自己. ltmp = i;//更新ltmp,维护以这个结尾的区间的左端点.if (res < dp[i]){res = dp[i];r = i;l = ltmp;}}if (res < 0){res = 0;l = 1;r = n;}cout << res <<' '<< a[l] <<' '<< a[r] << endl;return 0;
}
2.7动态规划之四边形不等式优化(明天写)
2.8动态规划之01背包问题
经典的背包问题包括:
01背包；部分背包；完全背包；多重背包；分组背包；混合背包；
同时这些也是会在本博客中讲解到的。
01背包问题描述:
有 N N N件物品和一个容量为 C C C的背包。第 i i i件物品的费用是 w [ i ] w[i] w[i]，价值是 v [ i ] v[i] v[i]，求将哪些物品装入背包可使价值总和最大。
思路分析:
如果在选择装入背包的物品时，对每种物品 i i i只有两种选择：装入背包或不装入背包，则称为01背包问题。
0-1背包问题是一个特殊的整数规划问题。
max ∑ i = 1 n v i x i { ∑ i = 1 n w i x i ≤ C x i ∈ { 0 , 1 } , 1 ≤ i ≤ n \max \sum_{i=1}^{n} v_i x_i \quad \left\{ \begin{aligned} % 使用aligned环境来对齐约束条件 \sum_{i=1}^{n} w_i x_i \le C \\ x_i \in \{0,1\}, \quad 1 \le i \le n \end{aligned} \right. maxi=1∑nvixi⎩ ⎨ ⎧i=1∑nwixi≤Cxi∈{0,1},1≤i≤n
设所给0-1背包问题的子问题的最优值为 m ( i , j ) m(i,j) m(i,j)，即 m ( i , j ) m(i,j) m(i,j)是背包容量为 j j j，可选择物品为 1 ， 2 ， … ， i 1，2，…，i 1，2，…，i时01背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算 m ( i , j ) m(i,j) m(i,j)的递归式如下。
m ( i , j ) = { max { m ( i − 1 , j ) , m ( i − 1 , j − w i ) + v i } m ( i − 1 , j ) m(i,j)= \left\{ \begin{aligned} &\max \{m(i-1,j),m(i-1,j-w_i)+v_i\}\\ & m(i-1,j) \end{aligned} \right. m(i,j)={max{m(i−1,j),m(i−1,j−wi)+vi}m(i−1,j)
特点：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即 m [ i ] [ j ] m[i][j] m[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。则其状态转移方程便是上面的第一行的式子.
将前i件物品放入容量为j的背包中”，若只考虑第i件物品（放或不放），那么就可以转化为一个只牵扯前i−1件物品的问题。"
- 如果不放第i件物品，那么问题就转化为“前i−1件物品放入容量为j的背包中”，价值为 m [ i − 1 ] [ j ] m[i−1][j] m[i−1][j]；
- 如果放第i件物品，就转化为“前i−1件物品放入剩下的容量为 j − c [ i ] j−c[i] j−c[i]的背包中”，此时能获得的最大价值就是 m [ i − 1 ] [ j − w [ i ] ] + v [ i ] m[i−1][j−w[i]]+v[i] m[i−1][j−w[i]]+v[i]（通过放入第i件物品获得的价值）。
测试链接
代码示例:
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define Len 100003
typedef pair<int,int> PII;
int read()
{int f = 0, sum = 0;char ch = getchar();while (!isdigit(ch)) f |= ch == '-', ch = getchar();while (isdigit(ch)) sum = sum * 10 + (ch ^ 48), ch = getchar();return f ? -sum : sum;
}
int cost[103];
int value[103];
int dp[103][103];
int main()
{int t,m;t=read();m=read();for(int i=1;i<=m;i++){cost[i]=read();value[i]=read();}memset(dp,0,sizeof dp);for(int i=1;i<=m;i++){for(int j=0;j<=t;j++){dp[i][j]=dp[i-1][j];//不要if(j>=cost[i])dp[i][j]=max(dp[i][j],dp[i-1][j-cost[i]]+value[i]);}}cout<<dp[m][t]<<endl;return 0;
}
01背包还可以优化(使用跳跃点,使用空间优化),但是这个是期末速成就不花时间复习了,如果有时间的话再补上这一部分.
2.9动态规划之完全背包
一般问题描述:
有 N N N种物品和一个容量为 V V V的背包，每种物品都有无限件可用。第 i i i种物品的重量是 w [ i ] w[i] w[i]，价值是 v [ i ] v[i] v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
测试链接
一个非常暴力的简单直接的写法就是下面:
#include<bits/stdc++.h>
using namespace std;
int main()
{int n,c;cin>>n>>c;int values[n+2]={0};int cost[n+2]={0};for(int i=1;i<=n;i++){cin>>cost[i]>>values[i];}int dp[n+2][c+2];for(int i=0;i<n+2;i++){for(int j=0;j<c+2;j++)dp[i][j]=0;}for(int i=1;i<=n;i++)//考虑的物品个数{for(int j=0;j<=c;j++)//背包的容量{for(int k=0;k*cost[i]<=j;k++)//选取的物品的个数{dp[i][j]=max(dp[i][j],dp[i-1][j-k*cost[i]]+values[i]*k);}}}cout<<dp[n][c]<<endl;return 0;
}
就是因为是非常的暴力所以很遗憾他超时了.
现在必须考虑优化了:
对于 K K K的循环遍历其实是不用管的:
例如，要计算 dp[10] 使用物品$ i \ \ (cost=2, value=3)$：
当 j=2 时，$dp[2] = max(dp[2], dp[0] + value[i]) $
当 j=4 时， d p [ 4 ] = m a x ( d p [ 4 ] , d p [ 2 ] + v a l u e [ i ] ) − > d p [ 2 ] 已经考虑了物品 i dp[4] = max(dp[4], dp[2] + value[i]) -> dp[2] 已经考虑了物品 i dp[4]=max(dp[4],dp[2]+value[i])−>dp[2]已经考虑了物品i，这里相当于拿了两个物品 i
当 j=6 时， d p [ 6 ] = m a x ( d p [ 6 ] , d p [ 4 ] + v a l u e [ i ] ) − > d p [ 4 ] 已经考虑了物品 i dp[6] = max(dp[6], dp[4] + value[i]) -> dp[4] 已经考虑了物品 i dp[6]=max(dp[6],dp[4]+value[i])−>dp[4]已经考虑了物品i，这里相当于拿了三个物品 i 依此类推，这种递推关系$ dp[j] = max(dp[j], dp[j - cost[i]] + values[i]) $ 隐式地包含了选取任意个物品 i 的可能性。
所以前面的已经把可以放入多件考虑进去了,所以就和0,1背包差不多了.
简单数学表达一下:
f [ i , j ] = m a x ( f [ i − 1 , j ] , f [ i − 1 , j − v ] + w , f [ i − 1 , j − 2 ∗ v ] + 2 ∗ w , f [ i − 1 , j − 3 ∗ v ] + 3 ∗ w , . . . . . ) f [ i , j − v ] = m a x ( f [ i − 1 , j − v ] , f [ i − 1 , j − 2 ∗ v ] + w , f [ i − 1 , j − 3 ∗ v ] + 2 ∗ w , . . . . . ) 由上两式，可得出如下递推关系： f [ i ] [ j ] = m a x ( f [ i , j − v ] + w , f [ i − 1 ] [ j ] ) f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)\\ f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)\\ 由上两式，可得出如下递推关系： f[i][j]=max(f[i,j-v]+w , f[i-1][j]) f[i,j]=max(f[i−1,j],f[i−1,j−v]+w,f[i−1,j−2∗v]+2∗w,f[i−1,j−3∗v]+3∗w,.....)f[i,j−v]=max(f[i−1,j−v],f[i−1,j−2∗v]+w,f[i−1,j−3∗v]+2∗w,.....)由上两式，可得出如下递推关系：f[i][j]=max(f[i,j−v]+w,f[i−1][j])
这个代码和01背包的非优化写法很像啊!!!我们对比一下:注意下标
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j]=f[i-1][j]//完全背包问题`
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题`
所以最终的代码(01背包的空间压缩也加入进去了):
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}//f[j]一开始全为0,表示第一次(i=0)的答案//所以在空间压缩中f[i]是保存上一次的(i-1)的答案for(int i = 1 ; i<=n ;i++){for(int j = v[i] ; j<=m ;j++)//必须从下到大枚举{f[j] = max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m]<<endl;
}