算法基础精选题单 动态规划（dp）（区间dp）（个人题解）

2024-06-22 04:04
文章标签 算法 基础 动态 规划 dp 个人 题解 区间 精选 题单

本文主要是介绍算法基础精选题单 动态规划（dp）（区间dp）（个人题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

前言：

正文：

  题单：【237题】算法基础精选题单_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder.com)

NC50493 石子合并：

NC50500 凸多边形的划分：

NC235246 田忌赛马：

NC13230 合并回文子串:

NC16645 [NOIP2007]矩阵取数游戏：

NC207781 迁徙过程中的河流：

后记：

前言：

  这些dp对我来说就没那么简单了，但写过这些题目之后我确实对区间dp有了一个简单的认识，区间dp一般都是二维的，由第一维表示左端点，第二维表示右端点，且状态一般由区间长度小的转移而来，所以我们写dp的转移时第一层循环由len来从小枚举区间长度，第二层循环枚举区间的左端点l，右端点就可以直接表示为l+len-1（也可先枚举右端点，再从右端点往左枚举左端点），初始化和状态转移方程就得根据相应题目来了，在写这写题目时我也学会了其他的一些技巧，比如环形数组的题该如何写以及__int128的用法（用来处理一些暴long long）的情况。

正文：

  题单：【237题】算法基础精选题单_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder.com)

NC50493 石子合并：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[410],dp1[410][410],dp2[410][410],pre[410];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];}for(int i=1;i<=2*n;i++){pre[i]=pre[i-1]+a[i];}memset(dp1,127,sizeof(dp1));memset(dp2,0,sizeof(dp2));for(int j=1;j<=2*n;j++){for(int i=j;i>=1;i--){if(i==j)dp1[i][j]=dp2[i][j]=0;for(int k=i;k<j;k++){dp1[i][j]=min(dp1[i][k]+dp1[k+1][j]+pre[j]-pre[i-1],dp1[i][j]);dp2[i][j]=max(dp2[i][k]+dp2[k+1][j]+pre[j]-pre[i-1],dp2[i][j]);}//cout<<i<<" "<<j<<" "<<dp1[i][j]<<endl;}}ll ansn=0x3f3f3f3f,ansm=0;for(int i=1;i<=n;i++){ansn=min(ansn,dp1[i][i+n-1]);ansm=max(ansm,dp2[i][i+n-1]);}cout<<ansn<<endl<<ansm<<endl;return 0;
}

这题原型是比较经典的模板题，这题在原题上做了些修改，一是要求最小和最大的值，二是这是个环形的数组；对于一我们处理两个不同初值的dp数组， 分别求min,max，对于二我们则将数组扩大到2n，a[n+i]=a[i]，这样枚举就能表示环形数组的所有情况，不过最后我们求答案时也要枚举所有长度为n的区间dp值。

dp的初始状态为 dp[i][j]=0（i==j ）

dp的状态转移方程我们可以知道为:

dp[i][j]=dp[i,k]+dp[k+1,j]+pre[j]-pre[i-1]

其中dp[i][j]表示将从石头i到石头j合并的得分（dp1为最小，dp2为最大）（同理dp[i][k]及dp[j]），pre[j]-pre[i-1]为此次合并的得分，由前缀和表示。

由此得结果。

NC50500 凸多边形的划分：

#include<bits/stdc++.h>
using namespace std;
__int128 read(){//直接在函数里面实现读字符串操作更简洁__int128 res=0;//初始结果赋值0char scan[1005];scanf("%s",scan);for(int i=0;i<strlen(scan);i++)res*=10,res+=scan[i]-'0';//实现进位return res;//返回__int128类型
}
void print(__int128 num){//递归调用，实现从高位向低位输出if(num>9) print(num/10);putchar(num%10+'0');
}
__int128 a[55],dp[55][55];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){a[i]=read();}for(int l=3;l<=n;l++){for(int i=1;i+l-1<=n;i++){int j=i+l-1;dp[i][j]=1e30;for(int k=i+1;k<j;k++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);}}}print(dp[1][n]);return 0;
}

这题像是能量项链的变式。状态转移方程为下：

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])

画个图大家自己体会下（可能不是很形象）：

其中dp[i][j]表示将i到j点这个多边形分割后权值和的最小值(i,j在这里是一个表示首，一个表示尾)，

a[i]*a[k]*a[j]为这个三角形的权值。

由于要求最小值，所以初始化为最大数，在加上数据会暴long long ，所以这里就要用到__int128了，他可以表示-2^127~2^127大小的数，但不能直接输入输出，必须采用我代码中那样的自定义函数。

NC235246 田忌赛马：

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int a[N],b[N],g[N][N],dp[N][N];
bool cmp(int n1,int n2){return n1>n2;
}
int main(){int n,ans;cin>>n;for(int i=1;i<=n;++i)cin>>a[i];for(int i=1;i<=n;++i)cin>>b[i];sort(a+1,a+n+1,cmp),sort(b+1,b+n+1,cmp);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){if(a[i]>b[j]) g[i][j]=200;else if(a[i]==b[j]) g[i][j]=0;else g[i][j]=-200;}for(int i=1;i<=n;++i){dp[i][0]=dp[i-1][0]+g[n-i+1][i];dp[i][i]=dp[i-1][i-1]+g[i][i];for(int j=1;j<i;++j) dp[i][j]=max(dp[i-1][j]+g[n-i+j+1][i],dp[i-1][j-1]+g[j][i]);}ans=dp[n][1];for(int i=2;i<=n;++i)ans=max(ans,dp[n][i]);cout<<ans<<endl;return 0;
}

首先给国王和田忌的马从小到大排序

接下来是贪心策略：

  1. 首先比最快的马，如果能赢就直接赢。
  2. 如果赢不了，就比国王和田忌最慢的马，能赢就赢。
  3. 如果最慢的马也赢不了，就用最慢的马去对国王最快的马。

设dp[i][j]表示齐王按从强到弱的顺序出马和田忌进行了i场比赛之后，从""头""取了j匹较强的马，从""尾""取了i-j匹较弱的马，所能获得的最大盈利。

其中g[i][j]表示田忌的马和齐王的马分别按照由强到弱的顺序排序之后，田忌的第 i 匹马和齐王的第 j 匹马赛跑所能取得的盈利，胜为 200 ，负为 −200 ，平为 0。

得状态转移方程为：

dp[i][j]=max(dp[i-1][j]+g[n-i+j+1][i],dp[i-1][j-1]+g[j][i]

NC13230 合并回文子串:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+5;
char a[N],b[N];
ll dp[55][55][55][55];
int main(){int t;cin>>t;while(t--){memset(dp,0,sizeof(dp));int ans=0;scanf("%s",a+1);scanf("%s",b+1);int sa=strlen(a+1),sb=strlen(b+1);for(int x=0;x<=sa;x++){for(int y=0;y<=sb;y++){for(int i=1,j=x;j<=sa;i++,j++){for(int k=1,l=y;l<=sb;k++,l++){if(x+y<=1) dp[i][j][k][l]=1;else{if(a[i]==a[j]) dp[i][j][k][l]|=dp[i+1][j-1][k][l];if(b[k]==b[l]) dp[i][j][k][l]|=dp[i][j][k+1][l-1];if(a[i]==b[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1];if(b[k]==a[j]) dp[i][j][k][l]|=dp[i][j-1][k+1][l];}if(dp[i][j][k][l])ans=max(ans,x+y);}}}}cout<<ans<<endl;}return 0;
}

初始状态只有一个字母的状态一定是回文。

假设A[i] ~ A[j]与B[k] ~ B[l]构成了一个回文串(这里设dp[i][j][k][l])，则他能转移到的区间有
1：a[i-1]==a[j+1]时 dp[i-1][j+1][k][l]
2：a[i-1]==b[l+1]时 dp[i-1][j][k][l+1]
3：b[k-1]==a[j+1]时 dp[i][j+1][k-1][l]
4：b[k-1]==b[l+1]时 dp[i][j][k-1][l+1]
那么对应的转移方程就为

if(a[i]==a[j]) dp[i][j][k][l]|=dp[i+1][j-1][k][l];

if(a[i]==b[l]) dp[i][j][k][l]|=dp[i+1][j][k][l-1];

if(b[k]==b[l]) dp[i][j][k][l]|=dp[i][j][k+1][l-1];

if(b[k]==a[j]) dp[i][j][k][l]|=dp[i][j-1][k+1][l];

NC16645 [NOIP2007]矩阵取数游戏：

#include<bits/stdc++.h>
using namespace std;
__int128 read(){//直接在函数里面实现读字符串操作更简洁__int128 res=0;//初始结果赋值0char scan[1005];scanf("%s",scan);for(int i=0;i<strlen(scan);i++)res*=10,res+=scan[i]-'0';//实现进位return res;//返回__int128类型
}
void print(__int128 num){//递归调用，实现从高位向低位输出if(num>9) print(num/10);putchar(num%10+'0');
}
typedef long long ll;
__int128 pow2(__int128 a,__int128 b){__int128 res=1;while(b){if(b&1)res*=a;a*=a,b/=2;}return res;
}
__int128 a[100][100];
__int128 dp[100][100][100];
int main(){ll n,m;__int128 ans=0;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=read();}}for(int k=1;k<=n;k++){for(int len=1;len<=m;len++){for(int i=1;i<=m,i+len-1<=m;i++){int j=i+len-1;if(i==j)dp[i][j][k]=a[k][i]*pow2(2,m-len+1);else dp[i][j][k]=max(dp[i+1][j][k]+a[k][i]*pow2(2,m-len+1),dp[i][j-1][k]+a[k][j]*pow2(2,m-len+1));//cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;}}//cout<<dp[1][m][k]<<endl;ans+=dp[1][m][k];}print(ans);return 0;
}

（自己独立思考写出来的，很有成就感）

因为每次只能取行首或者行尾，所以每行取得顺序都是独立的，由此可以从求最大的得分和转换成求每行的最大得分和。然后用区间dp计算每一行，状态转移方程为：

dp[i][j][k]=max(dp[i+1][j][k]+a[k][i]*pow2(2,m-len+1),dp[i][j-1][k]+a[k][j]*pow2(2,m-len+1))

k表示第几行.i,j表示区间，a[k][i]*pow2(2,m-len+1)表示取该数的得分，根据len来判断这次为第几次取数。

NC207781 迁徙过程中的河流：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005],dp[100005];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);dp[1]=a[1];dp[2]=a[2];for(int i=3;i<=n;i++){dp[i]=min(dp[i-1]+a[1]+a[i],dp[i-2]+a[1]+2*a[2]+a[i]);}cout<<dp[n];return 0;
}

说实话这题更像是线性dp，从题目中规律可以看出来在某个人要过河的时候要么是最快的那个人来接他，要么是还剩下两个让最快的把船开回来然后让这两个过去，之后让第二快的把船开过来，全部过去。这两个在题目中的样例里面都有体现。转移方程为：

dp[i]=min(dp[i-1]+a[1]+a[i],dp[i-2]+a[1]+2*a[2]+a[i])

后记：

  题对我确实很难，不过我也还算收获满满，写博客过程中也相当于是把写题过程在梳理了一遍，希望这篇博客不只能帮助到我自己吧。

这篇关于算法基础精选题单 动态规划（dp）（区间dp）（个人题解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1083235。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2