锐客网

  1. 首页 > it技术 > >

关于二维DP————站上巨人的肩膀

意匠惨淡经营中ing，
语不惊人死不休........
前几天学了DP，做了个简单的整理，记录了关于DP的一些概念之类的，今天记录一下刚学的一个类型
————关于二维DP
那建立二维数组主要是干嘛用的呢？？？其实就是是记录两个状态，（我也不是很清楚），然后再递推
直接上题吧

T1 、最长公共子序列：
好像有印象，之前做过一道类似的题，叫做最长上升子串，需要注意的是，这俩可不是很一样，人家子序列可以不连续，只要是相对顺序不改变就行，但是子串必须是连续的，针对这种题，我们联想起原来做题时想的状态转移方程，再加以改动就可以了：
f[i][j] 还是表示数组a的前i个元素和b数组的前j个元素能组成的最长子串的长度
那很容易以相同的方法联想到子序列，还是分情况讨论：
1、x[i]==y[j]时：f[i][j]=f[i-1][j-1]+1 （就是它们如果相等，长度就是不加上它们时组成的子串的长+1）
2、x[i]!=y[j]时：
1 2 3 4 5和2 3 5，这两个子串在 i=4,j=2 的时候，由于a[i]!=b[j]，加上它们俩和不加他们俩其实并不影响最长长度，所以i和j对应的他们以前这些元素（不包括i，j）能组成的最长长度其实和它们现在（包括i，j）能组成的长度是相同的（不必+1），所以当a[i]!=b[j]，它们对应的长度可以是f[i-1][j],也可以是f[i][j-1],取个max就好
再考虑边界，当一个字符串有0个元素时，它们的f[i][j]永远是0，所以f[0][j]=0 ，f[i][0]=0。
代码如下：

1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 int f[1001][1001]; 7 char x[1001],y[1001]; 8 int maxn; 9 int main() 10 { 11cin>>x; 12cin>>y; 13int m=strlen(x); 14int n=strlen(y); 15for(int i=0; if[i][j]? maxn:f[i][j]; 28} 29} 30printf("%d",maxn); 31return 0; 32 }



T2、编辑距离：
题意：有两个字符串，现在有三种操作：1、删除一个字符，2、插入一个字符，3、将一个字符改成另一个字符，现在要求要么花最少的字符操作次数，将字符串A转成B（只能操作A串）。
还是先设变量，f[i][j]表示把x[1~i]变为y[i~j]的最少操作次数，现在的目标就是求出状态转移方程：
还还还是分两种情况讨论：
当 x[i]==y[j] 时，那我们就可以不对它们进行操作了，也就是说我们直接让f[i][j]=f[i-1][j-1]
当 x[i]!=y[j] 时，我们有三种操作，需要分别求出他们的状态转移方程
1、删除 x[i]，那就是上一次的操作次数再加上1，即 f[i][j]=f[i-1][j]+1
2、给x[i]插入新字符：那就是相当于给y[j]删去一位，即 f[i][j]=f[i][j-1]+1
3、将x[i]变为y[j]：目前a数组的前i位和b数组的前j位都一样了，那其实就是给上一次的状态的基础上再操作一次，即f[i[[j]=f[i-1][j-1]+1
还有就是边界条件：当有一个数组为空时，我就全部插入（x数组为空），或全都输出（y数组为空），即 f[i][0]=i,f[0][j]=j
代码如下：

1 #include 2 #include 3 #include 4 using namespace std; 5 string a,b; 6 int ans; 7 int f[2001][2001]; 8 int main() 9 { 10cin>>a>>b; 11int lena=a.size(); 12int lenb=b.size(); 13for(int i=1; i<=lena; i++){ 14f[i][0]=i; 15} 16for(int i=1; i<=lenb; i++){ 17f[0][i]=i; 18} 19for(int i=1; i<=lena; i++){ 20for(int j=1; j<=lenb; j++){ 21if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]; 22else f[i][j]=min(min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+1); 23} 24} 25cout<



T3、机器分配问题（难得要命）
题目差不多就是说现在有n个公司，一共有m台，现在输入了一个n*m的矩阵，分别代表第i个公司如果分配j台机器的话的盈利，现在求最大盈利值，并输出每个公司应分配多少台机器
首先设一个二维数组f[i][j]代表前i个公司分配j台设备的最大盈利，那我们可以把f[i][j]分为两个阶段：
那就是把状态 i 分为前 i-1个公司和第 i 公司，设前 i-1 个公司分配了k个机器，那第 i 个公司就剩下了 j-k 台，我们让k从0到 j 挨个取一遍，求出最大值就好了，那状态转移方程就写出来了：
for( k=0 ; k<=j ; k++)
if ( f[i][j] <= f[i-1][k]+a[i][j-k] )
f[i][j] = f[i-1][k] + a[i][j-k]
那么我们这个a[i][j]咋来呀，仔细想一想，a[i][j]不就表示的是第 i 个公司分配 j 台机器的盈利吗，那就是我们要输入的那个二维数组呀！！！
那边界是啥？？？
当 i =0 时，f[0][j] 相当于 0 个公司分配 j 台机器，那最大利润就是 0 （连公司都没有，肯定不会有利润），即 f[0][j]=0
当 j =0 时，f[i][0] 相当于 i 个公司分配 0 台机器，那最大利润就是 0 （连机器都没有，肯定不会有利润），即 f[i][0]=0
你以为就这样愉快地结束了吗？？？
还要输出每个公司分配的机器数量呢，和原来咱求出最长上升子序列一样，咱还要记录用一个数组记录前驱，用于最后输出
实现起来就是这样的，如果 f[i][j] <= f[i-1][k]+a[i][j-k]，那么在给f[i][j]重新赋值的时候，我们顺便记录一下前驱，即p[i][j]=k,（代表前i-1个公司要用多少台机器）。在输出最大利润之后，从n到1开始递减，定义一个t=m（就是t台机器）来表示当前机器数量，建立一个ans数组来记录答案，先让 ans=t-p[i][t]，原因是t是当前的机器数量。减去p[i][t]（前i-1个用的机器数量），就是第 i 个公司用的机器数量，然后我让 t=p[i][t]代表前 i-1 个公司的用的机器总数，也就是让当前总数变成除去第i个公司用的机器后的机器的当前数量（因为我们现在已经不管第i个公司了，所以才要把它从总数量中除去使得目前的机器总数变成前 i-1 个的公司所用的机器总数）。然后重复以上操作，我们就得出了每个公司要用的机器数量，再输出就好了
代码放下面了
1 #include 2 #include 3 #include 4 #define int long long 5 using namespace std; 6 int ans=100000; 7 int a[1001][1001],f[1001][1001],p[1001][1001],ans1[1001]; 8 //a用于记录数据，f[i][j]代表前i个公司用了j台机器，p是代表第i个公司用了多少台电脑，ans1是答案 9 signed main() 10 { 11int n,m; 12scanf("%lld%lld",&n,&m); 13for(int i=1; i<=n; i++){ 14for(int j=1; j<=m; j++){ 15scanf("%lld",&a[i][j]); } 16} 17for(int i=0; i<=n; i++){ 18for(int j=0; j<=m; j++){ 19f[0][j]=0; 20f[i][0]=0; }//边界条件 21} 22for(int i=1; i<=n; i++) 23{ 24for(int j=0; j<=m; j++) 25{ 26for(int k=0; k<=j; k++) 27{ 28if(f[i][j]=1; i--) 39{ 40ans1[i]=t-p[i][t]; //记录第i个公司用了多少台 41t=p[i][t]; //表示当前去除第i个公司后的机器数量 42} 43for(int i=1; i<=n; i++){ 44cout<

T4、乘积最大（这是嫖的旁边的大佬的，所以这道题我是以大佬做题时思考的角度来写的）
直奔正题，分为几个步骤：
1、建立几个数组：①a数组代表我们想要得到的输入的数组，②f[i][j]代表1~i之间有j个乘号时状态的最大值
2、读入数组： 读题发现输入的是一个字符数组，遇到不要慌，我只要把它转成数字数组就好了，然后就写一个read函数来记录下来想要的a数组。
3、首先记录如果有0个乘号，那么那我们记录下来如果没有称号的话从1到i组成的 i 位数，
也就是
1 for(int i=1; i<=n; i++){ 2f[i][0]=f[i-1][0]*10+a[i]; 3}

4、现在我们来分析一下：
我们首先要明确一个前提，就是阶段后面都有一个乘号，而一个阶段里是只有数字的。
现在我已经处理到第f[i][j]这个状态了，画一个图：

这里有 j-1个乘号从第 l+1到第 i 个数字之间没有乘号，他们这些数共同构成了一个数当前的第i个数字
|————*...*...*....*——————————*|—————.......（都是数）.........————————————|(一个阶段后面必有一个乘号
1前j-1个乘号变量 l，也就是第j个乘号的位置当前状态：第i个数前面有j个1乘号

目前i前面有j个乘号，我们把这些乘号分成两段，一段是前 j - 1个乘号，另一段是第 j 个乘号，因为每隔一个乘号就会有两个数，所以前 j-1 个乘号间至少会有 j 个数，也就是说，状态f[i][j]前的那个乘号一定会在第j个数（能取到j）和第i个数（不能取到i）之间，那我们设一个变量 l ，为第 j 个乘号的位置，那么j <= l < i，这个发现会对找出状态转移方程发挥巨大作用，现在的目标就是找出状态转移方程：
当前状态我们要选取第 j 个乘号的位置，那就是取前 j-1 个乘号的阶段的状态 乘上 在 l~i 的位置的数组成的数，首先定义一个函数wucheng，这里代表从上一个乘号到下一个乘号之间的数字组合成的一个多位数（一位数字也有可能）,前面的状态是前 l个数字（为啥是前 l 个数字？看图）有j-1个乘号（j-1的原因是因为这个状态我又取了一个乘号，总共有j个，那前面的阶段就是j-1个），那就是f[l][j-1]，而从上个乘号到这个乘号之间的数就是从第 l-1 位到第 i 位的每个数字组成的一个数字wucheng(l+1,i)，他们俩一乘就是取了乘号后的状态，所以得到方程
f[i][j] = max( f[i][j]，f[l][j-1] * wucheng(l+1,i))
还有一点需要注意的是， j 不能无限加下去，一共只有 k 个乘号，所以 j 必须小于等于k，然后就没事了
OK，上代码
1 #include 2 #include 3 #include 4 #define ll long long 5 using namespace std; 6 ll n,k; //k代表总共输入多少乘号，n代表一共输入多少个数字 7 ll a[50]; 8 void read() 9 { 10char b=getchar(); 11while(b<'0'||b>'9') 12{ 13b=getchar(); 14} 15int cnt=1; 16a[cnt]=b-'0'; 17while(cnt<=n) 18{ 19b=getchar(); 20a[++cnt]=b-'0'; 21}//得到数组a 22 } 23 int f[50][10]; 24 int wucheng(int i,int j) 25 { 26int cnt=0; 27for(int l=i; l<=j; l++) 28{ 29cnt*=10; 30cnt+=a[l]; 31} 32return cnt; 33 }//定义这个函数，是为了记录从l到i之间的数字组成的那一个多（单）位数 34 int main(){ 35scanf("%d%d",&n,&k); 36read(); 37for(int i=1; i<=n; i++) 38{ 39f[i][0]=f[i-1][0]*10+a[i]; 40} 41for(int i=2; i<=n; i++)//从第一个数到最后一个数挨个枚举 42{ 43for(int j=1; j<=i-1&&j<=k; j++)//乘号个数，不能多余k个 44{ 45for(int l=j; l

T5、复制书稿
题目描述：输入两个数分别表示m本书和n个人抄，第二行输入m个数，表示每本书抄写所用的时间，现在让这n个人同时抄这些书，求如何分配才能使得总时间最少，要求：每个人抄的书几本必须是连续的，而且希望第一个人抄的最少，输出一共n行，每行代表第几个人抄的书是从第几本到第几本，中间用一个空格分隔
觉得这道题好像跟机器分配还是有些像的，还是设 f[i][j] 为前i个人抄写前j本书花的时间的最小值，也还是设前 i-1 个人抄了前 l 本书，第 i 个人抄了从第 l+1 到第 j 本书，再设一个二维数组 d来表示从抄第1本书到第 j 本书所用的时间，也就是前缀和，我需要提前求的，这样我们就能求得当只有一个人的时候抄书的时间（也算是找到起始数据）。
现在来讲讲思路，第一步肯定是求出这个他们当中花的时间最多的对吧，这就要用到DP，第二步要用贪心，因为我要保证第一个人花的时间最少（用贪心的原因是第一个人花时间最少的前提就是总时间最少，所以就是说第一个人花的时间的或多或少只要不会让时间变长，就不会影响最短的总时间，也就是说子问题最优解不会影响整个问题的最优解，所以用贪心），再从后往前递推就得到每个人的分配情况
所以现在有两个问题需要解决：1、怎么用DP？状态转移方程怎么写？2、怎么用贪心？ 怎么递推？
首先解决第一个问题：首先还是原来的老套路，用一个二维数组 f[i][j] 来表示前 i 个人抄了前 j 本书，也还是将 i 个人分成两段，第一段是前 i-1 个人，设他们抄了 l 本书，（因为每个人至少抄一本，那这些人抄的书 l 必须大于等于人数 i-1，而且一共只有j 本书，保证最后一个人还有书抄，l 必须小于 j，所以枚举 l 的时候范围就是 l=i-1; l 那为了求出最优解，我们就要求出抄书时间最长的人抄书的最短时间，首先比较前 i-1 个人抄书的最长时间（f[i-1][l]），与第 i 个人抄书的时间进行比较( f[1][j] - f[1][l]，我用前缀和表示的 )，得到最长的花的时间，再遍历每一个 l ，得到其中的最小值（因为我们想让这些人里抄书时间最长的人花的时间最少）
一点也不绕，我们很容易就能得到状态转移方程：
f[i][j] = min( f[i][j] ,max( f[i-1][l] , f[1][j] - f[1][l] ) )
然后就是第二个问题：贪心！
我用了一个DFS
1 void dfs(int i,int j,int t)//为了递推用的 2 { 3if(j==0)return ; 4if(if[k][m]) 5{ 6dfs(i,j-1,i); 7cout<
首先要明确的是，如果从后往前枚举，发现有一段的数字（抄书时间）之和小于等于最长时间而且再抄一本书就会超过最长时间，那这段数就是当前的人需要抄写的
首先头顶上的那三个变量中，j 代表目前有多少个人，i 和 t 代表从m开始枚举的两个数（我讲讲你就知道啥意思了，现在不太好说），i 一般是在 t 的前面。
如果只有0个人（j==0），直接返回。
现在我一直dfs并让i--，为啥呢？让 i 一直减减，如果 f[1][t]-f[1][i-1]>f[k][m]，（还是用的前缀和）我就可以从后往前找到两个数使得他们之间的数的和小于等于所有人抄书最长要用的时间（最长时间也就是 f[k][m]，我们刚才用DP求出来了，其中 k 代表我们要输入的人数，m 是我们要输入的书的本数）这样就能把这些数字当成一个人抄的书，之后让人数 j 减1，让当前的人分配到这些书。
或者是当 i < j 时，就说明要让多余书的个数的人分这些书，那肯定有人拿不着啊，由于不让划水，还是让人数 j 减1，代表这个人应该分配到这本书。
然而，如果不满足这两个限制，那你就继续 dfs(i-1,j,t)，直到找出满足这两个条件其中之一的数段
至于为啥要从后往前枚举，这样可以满足第一个人最少（可以自己想想）
代码如下：
1 #include 2 #define INF 0x3f3f3f 3 using namespace std; 4 int read(){ 5int x=0,f=1; 6char a=getchar(); 7while(a<'0'||a>'9'){ 8if(a=='-')f=-1; 9a=getchar(); 10} 11while(a>='0'&&a<='9'){ 12x*=10; 13x+=a-'0'; 14a=getchar(); 15} 16return x*f; 17 } 18 int m,k; 19 int a[510]; 20 int f[510][510]; 21 void dfs(int i,int j,int t)//为了递推用的 22 { 23if(j==0)return ; 24if(if[k][m]) 25{ 26dfs(i,j-1,i); 27cout<

记录的也不多，就先到这里吧
小生才疏学浅，孤陋寡闻，记录的东西也不算多好，以后会查缺补漏，愿日臻完善！
也十分感谢zyb大哥的帮助，这些题的思路包括代码实现都是人家资助的
再见！2022/3/20
关于二维DP————站上巨人的肩膀
文章图片

【关于二维DP————站上巨人的肩膀】

    推荐阅读


    上一篇：初识TypeScript一。

    下一篇：培训出来的程序员，要怎么熬过进去公司的第一个月（）