算法基础精选题单 动态规划（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;//初始结果赋值0
	char 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;//初始结果赋值0
    char 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])

后记：

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/743307.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

MySQL MVCC详解

MySQL MVCC详解

目录 前言 MVCC实现原理 UndoLog版本链 ReadView MVCC是否可以解决不可重复读与幻读 隔离级别 READ UNCOMMITTED - 读未提交与脏读 READ COMMITTED - 读已提交与不可重复读 REPEATABLE READ - 可重复读与幻读 SERIALIZABLE - 串行化 小结 前言 为了提高数据库并发能力…
阅读更多...
【Linux网络（一）初识计算机网络】

【Linux网络（一）初识计算机网络】

一、网络发展 1.发展背景 2.发展类型 二、网络协议 1.认识协议 2.协议分层 3.OSI七层模型 4.TCP/IP协议 三、网络传输 1.协议报头 2.局域网内的两台主机通信 3.跨网络的两台主机通信 四、网络地址 1.IP地址 2.MAC地址 一、网络发展 1.发展背景 计算机网络的发展…
阅读更多...
12 学习总结：操作符

12 学习总结：操作符

目录 一、操作符的分类 二、二进制和进制转换 &#xff08;一&#xff09;概念 &#xff08;二&#xff09;二进制 &#xff08;三&#xff09;进制转换 1、2进制与10进制的互换 &#xff08;1&#xff09;2进制转化10进制 &#xff08;2&#xff09;10进制转化2进制 2…
阅读更多...
手机照片回收站无法恢复图片怎么办？2个措施，找回丢失的相册

手机照片回收站无法恢复图片怎么办？2个措施，找回丢失的相册

我们的照片和视频存储在各种设备中&#xff0c;其中包括我们的智能手机&#xff0c;但有时候我们可能会不小心删除这些重要的数据。这时&#xff0c;手机照片回收站就显得尤为重要。然而&#xff0c;即使有回收站&#xff0c;我们也可能遇到一些问题&#xff0c;例如回收站中的…
阅读更多...
Geoserver源码解读四 REST服务

Geoserver源码解读四 REST服务

文章目录 文章目录 一、概要 二、前置知识点-FreeMarker 三、前置知识点-AbstractHttpMessageConverter 3.1 描述 3.2 应用 四、前置知识点-AbstractDecorator 4.1描述 4.2 应用 五、工作空间查询解读 5.1 模板解读 5.2 请求转换器解读 一、概要 关于geoserver的r…
阅读更多...
嘉立创EDA验证板复制下载

嘉立创EDA验证板复制下载

https://item.szlcsc.com/777208.html https://oshwhub.com/li-chuang-zhi-neng-ying-jian-bu/dc-dc在这里插入图片描述
阅读更多...
还能这样执行命令？命令执行绕过及防护规则研究

还能这样执行命令？命令执行绕过及防护规则研究

一、引言 我是渗透工程师->很多小伙伴在做攻防实战时发现有时在命令执行的payload中穿插单双引号命令也能执行成功&#xff0c;有时却又不行。那么到底在什么条件下用什么样的方式能实现对命令的切分呢&#xff1f;其中的原理又是如何&#xff1f;有没有其他绕过方式&#…
阅读更多...
常见的跨域场景

常见的跨域场景

我们在解决一个问题的时候应该先去了解这个问题是如何产生的&#xff0c;为什么会有跨域的存在呢&#xff1f;其实&#xff0c;最终的罪魁祸首都是浏览器的同源策略&#xff0c;浏览器的同源策略限制我们只能在相同的协议、IP地址、端口号相同&#xff0c;如果有任何一个不通&a…
阅读更多...
音视频入门基础：H.264专题（5）——FFmpeg源码中 解析NALU Header的函数分析

音视频入门基础：H.264专题（5）——FFmpeg源码中 解析NALU Header的函数分析

一、引言 FFmpeg源码中 通过h264_parse_nal_header函数将H.264码流的NALU Header解析出来。下面对h264_parse_nal_header函数进行分析。 二、h264_parse_nal_header函数定义 h264_parse_nal_header函数定义在FFmpeg源码&#xff08;下面演示的FFmpeg源码版本是5.0.3&#xff…
阅读更多...
【Linux】进程间通信_4

【Linux】进程间通信_4

文章目录 七、进程间通信1. 进程间通信分类systeam V共享内存消息队列 未完待续 七、进程间通信 1. 进程间通信分类 systeam V共享内存 进程间通信的本质就是让不同进程看到同一份资源。而systeam V是通过让不同的进程经过页表映射到同一块内存空间&#xff08;操作系统完成…
阅读更多...
Verilog描述一个带有异步置位和异步清零的D触发器

Verilog描述一个带有异步置位和异步清零的D触发器

1 带有异步置位和异步清零的D触发器的真值表&#xff1a; 2 Verilog代码描述 module DFF_SR(CLK, D, Rd, Sd, Q, QN);input CLK, D, Rd, Sd;output Q, QN;reg Q_DFF;always (posedge CLKor negedge Rd or negedge Sd)beginif(!Rd)Q_DFF < 1b0;else if(!Sd)Q_DFF < 1b1;e…
阅读更多...
硬盘监控和分析工具：Smartctl

硬盘监控和分析工具：Smartctl

文章目录 1. 概述2. 安装3. 使用4. smartctl属性信息介绍 1. 概述 Smartctl&#xff08;S.M.A.R.T 自监控&#xff0c;分析和报告技术&#xff09;是类Unix系统下实施SMART任务命令行套件或工具&#xff0c;它用于打印SMART自检和错误日志&#xff0c;启用并禁用SMRAT自动检测…
阅读更多...
永洪bi知识点

永洪bi知识点

1、下拉过滤组件和下拉参数组件的区别 下拉过滤组件只能对跟他绑有相同数据集的组件进行过滤 而下拉参数组件是当你设置了筛选条件以后&#xff0c;那么所有的组件&#xff0c;不管你绑定了什么样子的数据集&#xff0c;都能起作用&#xff0c;前提是你这个组件是需要去绑定参…
阅读更多...
docker基础使用教程

docker基础使用教程

1.准备工作 例子&#xff1a;工程在docker_test 生成requirements.txt文件命令&#xff1a;&#xff08;使用参考链接2&#xff09; pip list --formatfreeze > requirements.txt 参考链接1&#xff1a; 安装pipreqs可能比较困难 python 项目自动生成环境配置文件require…
阅读更多...
图片如何去水印，分享4个小妙招，手把手教会你！

图片如何去水印，分享4个小妙招，手把手教会你！

作为一个经常逛社区网站下载表情包、头像的人&#xff0c;遇到的一个大难题就是图片有水印。如何才能快速去除水印&#xff1f;询问了一圈身边朋友&#xff0c;搜集了各种资料&#xff0c;小编整理了4个超好用的方法。 如果大家和小编一样&#xff0c;能坐着就不站着&#xff0…
阅读更多...
【C++LeetCode】【热题100】移动零【简单】-不同效率的题解【4】

【C++LeetCode】【热题100】移动零【简单】-不同效率的题解【4】

题目&#xff1a; 暴力方法&#xff1a; class Solution { public:void moveZeroes(vector<int>& nums) {int counts0;//零的数量int swapCounts0;for(int i0;i<nums.size();i){if(nums[i]0){counts1;}}swapCountscounts;for(int i0;i<nums.size();i){fo…
阅读更多...
强制用户裸奔，微软新规以后用Win11必须先注册了

强制用户裸奔，微软新规以后用Win11必须先注册了

想必在座资深搞机佬对 Windows「本地账户」这一大功能都不陌生。 简单来说&#xff0c;本地用户账户是过去在安装操作系统时自动为大家创建的用于系统管理的默认内置账户。 「本地」二字&#xff0c;代表了即便在电脑不联网的情况下也能自动创建成功。 更重要的是它不与 Micr…
阅读更多...
优化了自制的浏览器主页的全屏功能

优化了自制的浏览器主页的全屏功能

第一次修改 <!DOCTYPE html> <html lang"zh-CN"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>全屏功能</title><style>…
阅读更多...
关于window的安装

关于window的安装

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 第一windows的分类 旗舰版 个人版…
阅读更多...
2024最新算法：北极海鹦优化（Arctic puffin optimization，APO）算法求解23个函数，MATLAB代码

2024最新算法：北极海鹦优化（Arctic puffin optimization，APO）算法求解23个函数，MATLAB代码

一、算法介绍 北极海鹦优化&#xff08;Arctic puffin optimization&#xff0c;APO&#xff09;算法是2024年提出一种智能优化算法。该算法模拟海鹦在空中飞行和水下觅食两个阶段的行为&#xff0c;旨在实现勘探与开发之间更好的平衡。该算法包括几个关键操作&#xff0c;包括…
阅读更多...
最新文章

Copyright @ 2022~2023