当前位置: 首页 > news >正文

算法复习(四、五、六)

动态规划

动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构、重叠子问题

关于动态规划算法和备忘录方法的适用条件:

要求:
用分治法和动态规划法分别解决最大子段和问题(第四步求最优解不需要掌握)

掌握用动态规划法解决0-1背包问题

最长单调递增子序列

最长公共子序列(会写出计算最长公共子序列长度的递推式即可)

矩阵连乘问题

备忘录做法:

signed main()
{cin>>n;for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;for(int i=1;i<=n;i++) dp[i][i]=0;for(int i=1;i<=n;i++)cin>>row[i]>>col[i];for(int i=1;i<=n;i++) p[i]=col[i];p[0]=row[1];for(int len=2;len<=n;len++){for(int i=1;i<=n-len+1;i++){int j=i+len-1;dp[i][j]=dp[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){int tmp=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];if(tmp<dp[i][j]){dp[i][j]=tmp;s[i][j]=k;}}}}cout<<dp[1][n]<<endl;dfs(1,n);return 0;
}

动态规划做法:

signed main()
{cin>>n;for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;for(int i=1;i<=n;i++) dp[i][i]=0;for(int i=1;i<=n;i++)cin>>row[i]>>col[i];for(int i=1;i<=n;i++) p[i]=col[i];p[0]=row[1];for(int len=2;len<=n;len++){for(int i=1;i<=n-len+1;i++){int j=i+len-1;dp[i][j]=dp[i][i]+dp[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){if(dp[i][j]>dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]){dp[i][j]=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];s[i][j]=k;}}}}cout<<dp[1][n]<<endl;print(1,n);return 0;
}

最大子段和问题

法一:

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e3+5;
const int inf=1e18;
int n,a[N],dp[N];signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=1;i<=n;i++){dp[i]=max(dp[i-1]+a[i],0ll);ans=max(ans,dp[i]);}cout<<ans<<endl;return 0;
}
/*
7
-2 11 -4 13 -5 -2 -100
*/

法二:

signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ans=0,b=0;for(int i=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];ans=max(ans,b);}cout<<ans<<endl;return 0;
}

法三:

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e3+5;
const int inf=1e18;
int n,a[N],dp[N];
int dfs(int l,int r)
{if(l==r)return a[l]>0?a[l]:0;int sum=0,mid=(l+r)/2;int left=dfs(l,mid);int right=dfs(mid+1,r);int s1=0,s2=0,tmp=0;for(int i=mid;i>=l;i--){tmp+=a[i];if(s1<tmp) s1=tmp;}tmp=0;for(int i=mid+1;i<=r;i++){tmp+=a[i];if(s2<tmp) s2=tmp;}sum=s1+s2;if(left>sum) sum=left;if(right>sum) sum=right;return sum;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cout<<dfs(1,n)<<endl;return 0;
}
/*
7
-2 11 -4 13 -5 -2 100
*/

01背包问题

int n,m,f[105][N],dp[N];void fun1()
{for(int i=1;i<=n;i++)   //物品i{for(int j=1;j<=m;j++)   //容量j{if(j<w[i])f[i][j]=f[i-1][j];else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);}}cout<<f[n][m]<<endl;
}
void fun2() //逆序更新
{for(int i=1;i<=n;i++){for(int j=m;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+c[i]);}
}

最长单调递增子序列

for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[j]<=a[i])dp[i]=max(dp[i],dp[j]+1);}}cout<<dp[n]<<endl;

最长公共子序列

{cin>>s1>>s2;len1=s1.length(),len2=s2.length();s1=" "+s1,s2=" "+s2;for(int i=1;i<=len1;i++){for(int j=1;j<=len2;j++){if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1,s[i][j]=1;else{if(dp[i-1][j]>dp[i][j-1]){dp[i][j]=dp[i-1][j];s[i][j]=2;//上面}elsedp[i][j]=dp[i][j-1];s[i][j]=3;}}}cout<<dp[len1][len2]<<endl;return 0;
}

贪心算法

适合于贪心算法求解的问题具有:贪心选择性质、最优子结构性质
贪心算法可以获取到问题的局部最优解,不一定能获取到全局最优解
掌握使用贪心算法解决:活动安排问题、背包问题、最优装载问题(件数最多)、删数问题

活动安排问题

按照结束时间进行排序

int n,p[N];
struct node
{int st,ed,id;
}a[N];
bool cmp(node a,node b)
{return a.ed<b.ed;
}
signed main()
{cin>>n;for(int i=1;i<=n;i++) {cin>>a[i].st>>a[i].ed;a[i].id=i;}sort(a+1,a+n+1,cmp);p[1]=1;int ans=1,tmp=a[1].ed;for(int i=2;i<=n;i++){if(a[i].st>=tmp){tmp=a[i].ed;ans++;p[i]=1;}}cout<<ans<<endl;return 0;
}

背包问题

int n,p[N];
struct node
{int w,v;double d;
}a[N];
bool cmp(node a,node b)
{return a.d>b.d;
}
signed main()
{cin>>n>>c;for(int i=1;i<=n;i++){cin>>a[i].w>>a[i].v;a[i].d=a[i].v/a[i].w;}sort(a+1,a+n+1,cmp);int i=1;double ans=0;while(i<=n&&a[i].w<=c){c-=a[i].w;ans+=a[i].v;i++;}if(i<=n) ans+=c*a[i].d;cout<<ans<<endl;return 0;
}

最优装载问题(件数最多)

重量轻的先装,找找重量从小到大进行排序

删数问题

找到最近下降点

#include <bits/stdc++.h>
#define int long longusing namespace std;
const int N = 7e6+100;
const int mod = 998244353;
int n,k;
string s;signed main()
{cin>>s>>k;n=s.length();if(k>=n)cout<<0<<endl;else{while(k){int i;for(i=0;i<s.length()&&s[i]<=s[i+1];i++);s.erase(i,1);k--;}while(s.size()>1&&s[0]=='0')s.erase(0,1);cout<<s<<endl;}return 0;
}
/**/

第六章

子集树实现素数环

const int N =1e6+5;
int n,a[N],vis[N],ans;
int check(int a,int b)
{int sum=a+b;for(int i=2;i*i<=sum;i++)if(sum%2==0)return 0;return 1;
}
void dfs(int x)
{if(x==n+1){if(check(a[1],a[n]))ans++;return;}for(int i=1;i<=n;i++){if(!vis[i]&&check(a[x-1],i)){vis[i]=1;a[x]=i;dfs(x+1);vis[i]=0;}}
}
void solve()
{cin>>n;dfs(1);cout<<ans<<endl;
}
signed main()
{solve();return 0;
}

排列树实现素数环

int n,a[N],vis[N],ans;
int check(int a,int b)
{int sum=a+b;for(int i=2;i*i<=sum;i++)if(sum%2==0)return 0;return 1;
}
void dfs(int x)
{if(x==n+1){if(check(a[1],a[n]))ans++;return;}for(int i=x;i<=n;i++){swap(a[x],a[i]);if(check(a[x-1],a[x]))dfs(x+1);swap(a[x],a[i]);}
}
void solve()
{cin>>n;for(int i=1;i<=n;i++) a[i]=i;dfs(1);cout<<ans<<endl;
}

装载问题

#include <bits/stdc++.h>
#define endl '\n'
#define int long longusing namespace std;
const int N =1e6+5;
const int inf=1e18;
int n,c,a[N],b[N],ans[N],sum,bestcw;
void dfs(int x,int cw)
{if(x==n+1){if(cw>bestcw){for(int i=1;i<=n;i++)ans[i]=b[i];bestcw=cw;}return;}sum-=a[x];if(cw+a[x]<=c){b[x]=1;cw+=a[x];dfs(x+1,cw);cw-=a[x];}if(cw+sum>bestcw){b[x]=0;dfs(x+1,cw);}sum+=a[x];
}
void solve()
{cin>>n>>c;for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];dfs(1,0);cout<<bestcw<<endl;for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<endl;
}
signed main()
{solve();return 0;
}

01背包问题(回溯+贪心)

剪枝规则:
约束函数:当选取一个物品时,累计的中部不可大于背包容量C
限界函数:根据物品单位重量的价值进行降序排列,越靠近树根位置剪掉分枝越多从而加快搜索;bound(i)定义为当前选取物品价值的和加上剩余物品的价值和,根据贪心的性质,剩余物品不会比贪心选取的物品方案更优,若bound(i)<=此时最优价值,则进行剪枝。

int n,c,cw,cv,bestv;
struct node
{int w,v;double d;
}a[N];
bool cmp(node a,node b)
{return a.d>b.d;
}
int check(int x)
{int v=cv;int tmp=c-cw;while(x<=n&&a[x].w<=tmp){tmp-=a[x].w;v+=a[x].v;x++;}if(x<=n)v+=1.0*tmp*a[x].w;return v;
}
void dfs(int x)
{if(x==n+1){bestv=cv;return;}if(cw+a[x].w<=c){cw+=a[x].w;cv+=a[x].v;dfs(x+1);cw-=a[x].w;cv-=a[x].v;}if(check(x+1)>bestv)dfs(x+1);
}
signed main()
{cin>>c>>n;for(int i=1;i<=n;i++){cin>>a[i].w>>a[i].v;a[i].d=a[i].v*1.0/a[i].w;}sort(a+1,a+n+1,cmp);dfs(1);cout<<bestv<<endl;return 0;
}
/*
50 3
10 60
30 120
20 100
*/

n皇后问题

int n,m,a[105][105],p[N],ans;
int check(int x)
{for(int i=1;i<x;i++)if(abs(x-i)==abs(p[x]-p[i])||(p[i]==p[x]))return 0;return 1;
}
void dfs(int x)
{if(x==n+1){ans++;for(int i=1;i<=n;i++)cout<<p[i]<<" ";cout<<endl;return;}for(int i=1;i<=n;i++){p[x]=i;if(check(x))dfs(x+1);}
}
signed main()
{cin>>n;dfs(1);if(ans)cout<<ans<<endl;elsecout<<"No Solution!"<<endl;return 0;
}

相关文章:

算法复习(四、五、六)

动态规划 动态规划算法的有效性依赖于问题本身所具有的两个重要性质&#xff1a;最优子结构、重叠子问题 关于动态规划算法和备忘录方法的适用条件&#xff1a; 要求&#xff1a; 用分治法和动态规划法分别解决最大子段和问题&#xff08;第四步求最优解不需要掌握&#xff…...

SORT与DeepSORT简介

一、MOT( mutil-object tracking)步骤 在《DEEP LEARNING IN VIDEO MUTIL-OBJECT TEACKING: A SURVEY》这篇基于深度学习多目标跟踪综述中&#xff0c;描绘了MOT问题的四个主要步骤 1.跟定视频原始帧 2.使用目标检测器如Faster-rcnn, YOLO, SSD等进行检测&#xff0c;获取目标…...

TCP/IP网络编程——多播与广播

完整版文章请参考&#xff1a; TCP/IP网络编程完整版文章 文章目录第 14 章 多播与广播14.1 多播14.1.1 多播的数据传输方式以及流量方面的优点14.1.2 路由&#xff08;Routing&#xff09;和 TTL&#xff08;Time to Live,生存时间&#xff09;&#xff0c;以及加入组的办法14…...

K8S DNS解析过程和延迟问题

一、Linux DNS查询解析原理&#xff08;对于调用glibc库函数gethostbyname的程序&#xff09;我们在浏览器访问www.baidu.com这个域名&#xff0c;dns怎么查询到这台主机呢&#xff1f;  1、在浏览器中输入www.baidu.com域名&#xff0c;操作系统会先查找本地DNS解析器缓存&a…...

【JavaScript】js实现深拷贝的方法

前言 在js中我们想要实现深拷贝&#xff0c;首先要了解深浅拷贝的区别。 浅拷贝&#xff1a;只是拷贝数据的内存地址&#xff0c;而不是在内存中重新创建一个一模一样的对象&#xff08;数组&#xff09; 深拷贝&#xff1a;在内存中开辟一个新的存储空间&#xff0c;完完全全…...

RK3288 GPIO记录

1、引脚对应的GPIO 编号第一种 使用/sys/kernel/debug/gpio查询所有gpio引脚的基数第二种 cat /sys/class/gpio/gpiochip248/label对应的label就是GPIO引脚&#xff0c;例如下图GPIO8对应的基数就是2482、计算编号编号 基数 PIN脚如GPIO8的基数是248&#xff0c; GPIO8_A6的编…...

MongoDB介绍及使用教程

文章目录一、MongoDB介绍1. 什么是MongoDB2. 为什么要用MongoDB3. MongoDB的应用场景4. MongoDB基本概念二、MongoDB使用教程1.下载安装&#xff08;Windows&#xff09;2.MongoDB Conpass简单使用&#xff08;选学&#xff09;3.使用navicat连接MongoDB4.JAVA项目中使用MongoD…...

51单片机开发环境搭建 - VS Code 从编写到烧录

我安装并测试成功的环境&#xff1a; 操作系统&#xff1a;Windows 10 (22H2)单片机&#xff1a;STC89C52RCPython version: 3.7.6 在这之前&#xff0c;给51单片机写程序是用 Keil 5&#xff08;编写编译&#xff09;、STC-ISP&#xff08;烧录&#xff09;&#xff0c;由于…...

python datetime、字符串和时间戳之间的相互转换12小时制和24小时制时间相互转化

文章目录1.字符串转datetime格式2.datetime转字符串3.时间戳转datetime格式4.datetime格式转时间戳5.应用&#xff1a;将12小时制的字符串转换为时间戳1.字符串转datetime格式 把字符串转换为datetime的格式 项目字符串的样子‘%m/%d/%Y %H:%M:%S’2/3/2023 15:30:20‘%m-%d-…...

百度百科词条怎么做?百度百科词条创建攻略分享

只要是想要将自己宣传出去的企业或是个人&#xff0c;都建议创建属于自己的百度百科词条&#xff0c;因为百度百科词条流量大、权重高、排名靠前&#xff0c;创建百度百科词条可以提高企业或是个人的知名度和口碑。 百度百科词条怎么做&#xff1f;每天都有用户在百度上搜索这…...

基于Hive的河北新冠确诊人数分析系统的设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…...

k8s二进制部署

目录 一、环境准备 常见的k8s部署方式 关闭防火墙 关闭selinux 关闭swap 根据规划设置主机名 在master添加hosts 将桥接的IPv4流量传递到iptables的链 时间同步 二、部署etcd集群 1、master节点部署 #查看证书的信息 上传etcd-cert.sh 和etcd.sh 到/opt/k8s/ 目录…...

Windows出现0xc00d36e5错误怎么办?

当我们使用Windows Media Player来播放视频文件时&#xff0c;可能会出现无法播放&#xff0c;并显示0xc00d36e5错误代码。该错误可能是因为Windows Media Player不支持视频格式、注册表项损坏、系统配置问题、第三方应用程序冲突等。下面将开始介绍0xc00d36e5错误的解决方法&a…...

Idea搭建Spring5.3.x源码阅读环境

1. 概述 Spring是一个轻量级Java开源框架&#xff0c;在Java项目开发过程中已经离不开Spring全家桶了&#xff0c;包括Spring、SpringBoot、SpringCloud等&#xff0c;学习好Spring基础源码也有助于更好在项目中使用Spring相关组件&#xff0c;在学习源码前需要搭建好源码学习…...

2.20jdbc

一.数据库编程的必备条件编程语言:java c c Python数据库 Oracle,MySQL,SQL Server数据库驱动包:不同的数据库,对应不同的编程语言提供了不同的数据库驱动包:MySQL提供了Java的驱动包mysqlconnector-java,需要就Java操作MySQL需要该驱动包二.Java的数据库编程JDBC&#xff0c;即…...

【代码随想录训练营】【Day19休息】【Day20】第六章|二叉树|654.最大二叉树|617.合并二叉树|700.二叉搜索树中的搜索|98.验证二叉搜索树

最大二叉树 题目详细&#xff1a;LeetCode.654 这道题在题目几乎就说明了解题的思路了&#xff1a; 创建一个根节点&#xff0c;其值为 nums 中的最大值&#xff1b;递归地在最大值左边的子数组上构建左子树&#xff1b;递归地在最大值右边的子数组上构建右子树&#xff1b;…...

华为云计算之容灾技术

容灾是物理上的容错技术&#xff0c;不是逻辑上的容错同步远程复制&#xff1a;主备距离≤200km&#xff0c;只有在主备设备上都写成功&#xff0c;才会告诉主机写成功&#xff0c;不会丢失数据异步远程复制&#xff1a;主备距离&#xff1e;200km&#xff0c;只要主设备上写成…...

React系列之Redux

1 Redux概述 Redux 是 JavaScript 状态容器&#xff0c;提供可预测化的状态管理。Redux中文文档 Redux 和react没有必然关系&#xff0c;redux可以应用于各种框架&#xff0c;包括jquery&#xff0c;甚至js都可以使用redux&#xff0c;只不过redux和react更加搭配。redux也推…...

最简单得方法解决TCP分包粘包问题

如何用最简单的方法解决TCP传输中的分包粘包问题&#xff1f; 首先需要说明一点&#xff0c;分包粘包等等一系列的问题并不是协议本身存在的问题&#xff0c;而是程序员在写代码的时候&#xff0c;没有搞清楚数据的边界导致的。 看个简单的例子&#xff0c;TCP客户端不断的向服…...

免费使用通配符域名证书

文章目录前言一、手动安装acme.sh操作1、安装acme.sh2、使用dns api自动续签二、宝塔自动操作【推荐】总结前言 之前个人站点一般都是使用阿里云免费单域名证书&#xff0c;虽然好用但是只有一年有效&#xff0c;到期只能手动重新申请&#xff0c;并且每次弄个子域名出来就要重…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...