程序员经验分享-hwhale

题解 . 洛谷题单之动态规划的引入

2023-10-28

前置知识：

数字三角形问题：动态规划之数字三角形模型_如何何何的博客-CSDN博客

01背包问题：动态规划之01背包模型_如何何何的博客-CSDN博客

完全背包问题：动态规划之完全背包模型_如何何何的博客-CSDN博客

多重背包问题：动态规划之多重背包模型_如何何何的博客-CSDN博客

题1. 数字三角形 Number Triangles

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

数字三角形裸题。

AC代码如下：

#include<iostream>
#include<cstring>
using namespace std;

const int N = 510;
int g[N][N], f[N][N];//三角形，以每个点为终点的路径的最大值
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)//读入地图（其实可以在读入的时候就处理，这里将读入和处理分开了）
        for (int j = 1; j <= i; j++)
            cin >> g[i][j];

    memset(f, -0x3f, sizeof f);//初始化
    f[1][1] = g[1][1];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            if (j - 1 >= 1)f[i][j] = max(f[i][j], f[i - 1][j - 1] + g[i][j]);//如果左上角未越界
            if (j < n)f[i][j] = max(f[i][j], f[i - 1][j] + g[i][j]);//如果右上角未越界
        }

    int res = -0x3f3f3f3f;//在最后一行中找最大值
    for (int i = 1; i <= n; i++)res = max(res, f[n][i]);

    cout << res;
    return 0;
}

题2. 采药：

P1048 [NOIP2005 普及组] 采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

01背包裸题。

AC代码如下：

#include<iostream>
using namespace std;
const int N=1010;
int f[N];
int main(){
    int t,n;//读入时间和草药数量
    int v,w;//时间和价值
    cin>>t>>n;
    for(int i=1;i<=n;i++){//枚举前n株草药
        cin>>v>>w;//读入当前草药的时间和价值
        for(int j=t;j>=v;j--)//滚动数组
            f[j]=max(f[j],f[j-v]+w);
    }
    cout<<f[t];
    return 0;
}

题3. 挖地雷:

P2196 [NOIP1996 提高组] 挖地雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

数据范围较小，可以使用dfs；

dp做法：最长上升子序列模型，f[i]表示以 i 点为结尾的路径的最大值；

由题可知图为拓扑图，每一层所有点的状态都是由上一层的点更新得到，故按层次枚举即可；

由题可知编号小的点连向编号大的点，不存在编号大的点连向编号小的点，故根据编号从小到大枚举即可；

记录每个点的前驱即可得到路径。

AC代码如下：

#include<iostream>
#include<vector>
using namespace std;
const int N=25;
int p[N];//地雷数
int f[N];//状态
int pre[N][N];//每个点的前驱
int path[N];//前驱路径 

int main(){
	int n;
	cin>>n;
	
	//地雷数 
	for(int i=1;i<=n;i++)cin>>p[i];
	
	//每个点的前驱 
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			cin>>pre[j][i];
	
	for(int i=1;i<=n;i++){
		f[i]=p[i];
		path[i]=i;
		
		for(int j=1;j<i;j++)
			//如果i点状态被更新 
			if(pre[i][j]) 
				if(f[i]<f[j]+p[i]){f[i]=f[j]+p[i];path[i]=j;}
	}
	
	int res=0,k=0;
	for(int i=1;i<=n;i++)
		if(res<f[i]){res=f[i];k=i;}
	
	vector<int>v;
	bool flag=false;
	while(1){
		if(path[k]==k)flag=true;
		v.push_back(k);
		k=path[k];
		if(flag)break;
	} 
	
	for(int i=v.size()-1;i>=0;i--)cout<<v[i]<<" ";
	cout<<endl<<res;
	return 0;
}

题4. 滑雪：

P1434 [SHOI2002] 滑雪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

类似数字三角形模型，f[i][j] 表示 ( i , j ) 点的最大长度；

f[i][j] 由上下左右四个方向转移得到，并且可知高度低的点一定由高度高的点转移得到；

故可以将所有点按照高度进行排序，然后两重循环进行状态更新，第一重从大到小枚举所有点，第二重枚举所有较高的点来做更新；

注意：相同高度的不能滑过去。

AC代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int g[N][N];
int f[N][N]; 
int n,m;
//点的坐标及其高度 
struct pp{
	int x,y,h;
}p[N*N];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; 

bool cmp(struct pp a,struct pp b){
	return a.h>b.h;
}

int main(){
	cin>>n>>m;
	int k=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			p[k].x=i,p[k].y=j,p[k++].h=g[i][j];
		}
	//从大到小排 
	sort(p,p+n*m,cmp);
		
	
	for(int i=0;i<n*m;i++){//从大到小枚举所有点 
		f[p[i].x][p[i].y]=1;
		//枚举所有较高的 
		for(int j=0;j<i;j++){
			//相同高度 
			if(p[j].h==p[i].h)continue;
			//该点是否可用 
			bool flag=false;
			for(int m=0;m<4;m++)
				if(p[j].x+dx[m]==p[i].x&&p[j].y+dy[m]==p[i].y)flag=true;
				
			if(flag)
				f[p[i].x][p[i].y]=max(f[p[j].x][p[j].y]+1,f[p[i].x][p[i].y]);
		}
	}
	
	int res=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)res=max(res,f[i][j]);
		
	cout<<res;
	return 0; 
}

题5 . 最大食物链计数：

P4017 最大食物链计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

f[i] 表示以 i 号点结尾的食物链数量，f[i] 由 i 点上一层的点转移得到（上一层点的状态之和）；

食物网为拓扑图，但无法直接按层次遍历，存在如下反例，直接按层次遍历答案为1：

暂时未写，后续补充。

题6. 最大子段和：

P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

双指针，DP；

DP解法：

f [i] 表示以 i 号位置的数字结尾的最大子段和；

状态转移方程：f[i] = max ( f[i-1] + a[i] , a[i] )。

AC代码如下：

#include<iostream>
using namespace std;
const int N=2*1e5+10;
int f[N];

int main(){
	int n;
	cin>>n;
	
	int res=-0x3f3f3f3f;
	for(int i=0;i<n;i++){
		cin>>f[i];
		f[i]=max(f[i],f[i-1]+f[i]);
		res=max(res,f[i]);
	}
	
	cout<<res;
}

题7. 5倍经验日：

P1802 5 倍经验日 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

01背包问题；

f[i][j] 表示打 第 i 个人，且有 j 瓶药的最大经验；

状态转移：f[i][j] = max( f[i-1][j] + l[i]，f[i-1][j-1] + w[i] )。

AC代码如下：

#include<iostream>
using namespace std;
const int N=1010;
int w[N],s1[N],s2[N];
long long f[N][N];

int main(){
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)
        cin>>s1[i]>>s2[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j]+s1[i];
            if(j>=w[i])f[i][j]=max(f[i][j],f[i-1][j-w[i]]+s2[i]);
        }
        
    cout<<f[n][m]*5;
    
}

题8. 过河卒：

P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

f[i][j] 表示走到 ( i , j ) 的路径数量；

状态转移：只能从左上角走到，f[i][j] = f[i-1][j] + f[i][j-1]。

AC代码如下：

#include<iostream>
using namespace std;
int n,m,x1,y1;
const int N=25;
long long f[N][N];
int main(){
    f[0][1]=1;
    cin>>n>>m>>x1>>y1;
    n++,m++,x1++,y1++;   
int dx[] = { -2, -1, 1, 2, 2, 1, -1 ,- 2,0 }, dy[] = {  1,2, 2, 1, -1,- 2,- 2, -1,0 };
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int st=0;
            for(int u=0;u<9;u++)
                if(i==x1+dx[u]&&j==y1+dy[u])st=1;
            if(st==1)f[i][j]=0;
            else f[i][j]=f[i-1][j]+f[i][j-1];
        }
    f[1][1]=0;
    cout<<f[n][m];
    return 0;
}

题9. 装箱问题：

P1049 [NOIP2001 普及组] 装箱问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

01背包裸题。

AC代码如下：

#include<iostream>
using namespace std;
const int N=20010;
int f[N];
int n,V;

int main(){
	cin>>V>>n;
	for(int i=1;i<=n;i++){
		int v;
		cin>>v;
		for(int j=V;j>=v;j--)
			f[j]=max(f[j],f[j-v]+v);
	}
	cout<<V-f[V];
	return 0;
}

题10. 疯狂的采药：

P1616 疯狂的采药 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

完全背包问题裸题。

AC代码如下：

#include<iostream>
using namespace std;

const int N=1e7+10;
long long f[N];

int main(){
    int n,m;
    cin>>n>>m;//时间与数量
    
    int t,s;
    for(int i=1;i<=m;i++){
        cin>>t>>s;
        
        for(int j=t;j<=n;j++)
            f[j]=max(f[j],f[j-t]+s);
    }
    
    cout<<f[n];
    
    return 0;

}

题11. 小A点菜：

P1164 小A点菜 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

01背包问题：

f[i][j] 表示只考虑前 i 道菜，花掉 j 元的方案数；

状态转移方程 f[i][j] = f[i-1][j] + f[i-1][j-w[i]]。

AC代码如下:

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
int a[N];
int n,m;//n种菜m元钱
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    
    f[0][0]=1;
        
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            if(j>=a[i])f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
            else f[i][j]=f[i-1][j];
        }
        
    cout<<f[n][m];
    return 0;
}

题12. 摆花：

P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

多重背包问题；

f[i][j] 表示只选前 i 种花，共有 j 盆花的选法；

状态转移方程：f[i][j] += ( f[i-1][j] + f[i-1][j-1] + f[i-1][j-2] + …… + f[[i-1][j-a[i]] ) 。

AC代码如下：

#include<iostream>
using namespace std;
const int N=110,mod=1e6+7;
int f[N][N];

int main(){
	int n,m;
	cin>>n>>m;
	
	f[0][0]=1;
	for(int i=1;i<=n;i++){//前i种花 
		int a;
		cin>>a;
		for(int j=0;j<=m;j++){//总共j盆花 
			for(int k=0;k<=a&&k<=j;k++){//选k盆i种花
			    f[i][j]+=f[i-1][j-k];	 
			    f[i][j]%=mod;
			}
		}
	}
	
	cout<<f[n][m];	
	return 0;
}

题12. 线段：

P3842 [TJOI2007]线段 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

f[i][0] 表示走完第 i 行的线段后停在线段左端的最短步数，f[i][1] 表示走完第 i 行的线段后停在线段右端的最短步数；

假设 a[i][0] 表示第 i 行的线段左端点，a[i][1] 表示第 i 行的线段右端点；

状态转移：第 i 行的端点状态由第 i-1 行的左端点或右端点转移得到，一共两种情况，取最小值即可。

AC代码如下：

#include<iostream>
#include<cmath>
using namespace std;
const int N=1e4*2;
int f[N][2],g[N][2];

int main(){
	int n;
	cin>>n;
	
	f[0][0]=f[0][1]=0;//初始0步 
	g[0][0]=g[0][1]=1;//初始位置为1 
	
	for(int i=1;i<=n;i++){
		cin>>g[i][0]>>g[i][1];
		
		f[i][0]=min(
					//上一层左端点转移得到
					f[i-1][0] + 1 + (g[i][1]-g[i][0]) + abs(g[i-1][0]-g[i][1]), 
					//上一层右端点转移得到
					f[i-1][1] + 1 + (g[i][1]-g[i][0]) + abs(g[i-1][1]-g[i][1])
					);
		f[i][1]=min(
					//上一层左端点转移得到 
					f[i-1][0] + 1 + (g[i][1]-g[i][0]) + abs(g[i-1][0]-g[i][0]),
					//上一层右端点转移得到 
					f[i-1][1] + 1 + (g[i][1]-g[i][0]) + abs(g[i-1][1]-g[i][0])
					);
		
	}
	
	int res;
	res=min( f[n][0]+abs(g[n][0]-n),f[n][1]+abs(g[n][1]-n) );
	cout<<res-1;
	return 0; 
}

题13. 金明的预算方案：

P1064 [NOIP2006 提高组] 金明的预算方案 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

暂时未写，后续补充。

题14. kkksc03考前临时抱佛脚：

P2392 kkksc03考前临时抱佛脚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：

搜索、DP；

DP解法：

01 背包问题，对于每个题目有写与不写两种情况；

对于每个科目，尽量平均分为两部分；

将做题时间看做体积和价值，即求一半容量下能装下的物品的最大价值是多少；

AC代码如下：

#include<iostream>
#include<cstring>>
using namespace std;
const int N=25;
int f[N][N*60];
int a[N];
int b[N];

int main(){
	//每组题目的数量 
	for(int i=0;i<4;i++)cin>>a[i];
	
	int res=0;
	//4组物品 
	for(int i=0;i<4;i++){
		//总体积为v 
		int v=0;
		for(int j=1;j<=a[i];j++){cin>>b[j];v+=b[j];}
		
		//01背包
		memset(f,0,sizeof f);
		
		for(int j=1;j<=a[i];j++)
			for(int k=0;k<=v;k++){
				f[j][k]=f[j-1][k];
				if(k>=b[j])f[j][k]=max(f[j][k],f[j-1][k-b[j]]+b[j]);
			} 
		res+=(v-f[a[i]][v/2]);
		
	}
	
	cout<<res;
	return 0;
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

动态规划

算法

c

蓝桥杯

数据结构

题解 . 洛谷题单之动态规划的引入 的相关文章

随机推荐

  • 基于MATLAB的线激光三维彩色扫描仪

    暑期做的一个项目 开始并不是很熟悉 在网上查找的资料也不是很具体 但是自习学习了理论知识之后还是比较容易的做出来这个项目 现在开源整个项目 由于篇幅有限 本文适合稍微有点点基础的朋友 源码见底部 先显示下最后结果 一 硬件设计 主要有步进电

  • struts2与hibernate整合遇到的问题

    1 问题描述 今天练习struts2和hibernate整合 结果各层都写好了浏览器还出现了service实例空指针的错误 控制台只是提示没有找到什么值栈啊什么的 解决过程 查看各层代码 配置文件是否写的有问题 都没问题 后来就找是不是包的

  • 如何登录GItHub

    1 找到hosts 2 用管理员权限运行 3 打开终端 4 执行cmd 5 再执行notepad hosts 6 会自动弹出hosts 7 查找3个需要添加在hosts最后的内容 1 github com IP地址查询 https gith

  • Pandas常用函数操作示例

    一 概述 本文主要记录一些常用的pandas 操作示例 可收藏用作日常编码中的速查手册 用到的示例可以在下面的索引分类中找到 二 目录 文章目录 一 概述 二 目录 三 示例 1 pandas 创建 Series 通过 list 创建 se

  • CentOS7 学习 10 常用指令 7 压缩、解压缩

    索引 gzip 压缩 gunzip 解压 zip 压缩 unzip 解压 在项目打包发布中常用 这个和windows一样 tar zcvf xx tar gz 要压缩的文件file tar zxvf xx tar gz C 解压到的路径di

  • ELK日志收集系统

    Kibana 数据分析工具 提供数据的聚合 分析功能 数据的可视化 用图表展现数据 分析图标可进行分享 或在web应用中引用图表 Kibana汉化 docker cp kibana usr share kibana config kiban

  • 一篇“从入门到上手”的PCB设计教程

    一篇 从入门到上手 的PCB设计教程 这是一篇面向神马都不懂的小白玩家的PCB设计教程 希望能帮助大家快速上手PCB的设计 1 预备知识 1 1 常用工具 1 做图工具 Altium Designer 2 PCB板加工 嘉立创 3 元件封装

  • react的onClick自动触发等相关问题

    react分页组件遇到的问题 private getFirst const pageNo this state if pageNo gt 3 return span 首页 span else return private changePag

  • 基于openlayers的最短路径规划

    之前的文章讲到了如何构建空间数据库 矢量数据如何入库 如何构建拓扑网络 如何自定义查询函数 如何构建wms服务 本文讲解如何基于openlayers晚上最短路径规划功能 一 基于openlayers3 1 构建网页 这里只是一个简单的网页

  • idea 创建mybatis xml文件时找不到

    1 File gt Settings 如图 2 添加模板 如下图 3 添加xml模板 如下图 模板内容

  • 编译openwrt全过程（超详细）

    本教程的编译环境 win7 专业版 VMwareWorkstation6 5虚拟机 Ylmf OS 3 0 编译的过程中要保持电脑联网 搭建编译环境 应用程序 附件 终端 sudo apt get update 更新 安装编译需要的组件 s

  • 前端最新一面

    vue2 vue3 v model的区别 instance of原理 事件循环机制打印顺序 打印结果 1 3

  • 手机上编写Java程序的软件

    对于程序员来说 编写代码几乎都是在电脑上 但有时候在一些特殊情况下 没有电脑 或者不方便带电脑 这时就想 要是能在手机上写代码该多好啊 以前我也折腾过 找过许多软件 但感觉不如我意 但我并没有放弃 在浏览YouTube的时候 偶然发现了一款

  • 低功耗技术（三）UPF的使用

    UPF是一个统一的 被广泛应用的低功耗实现标准 它用一些标准的语言描述用户的低功耗设计意图 一 UPF所需要的特殊单元库 1 Level Shifter和Isolation Cell 对于多电压设计 需要用Level shifter来实现不

  • SpringBoot整合JWT和MD5实现单点登录

    1 知识点 1 1 JWT JSON Web Token JSON Web令牌 是一个开放标准 rfc7519 它定义了一种紧凑的 自包含的方式 用于在各方之间以JSON对象安全地传输信息 此信息可以验证和信任 因为它是数字签名的 jwt可

  • Android开发实践：Java层与Jni层的数组传递

    http www linuxidc com Linux 2014 03 97561 htm Android开发中 经常会在Java代码与Jni层之间传递数组 byte 一个典型的应用是Java层把需要发送给客户端的数据流传递到Jni层 由J

  • 边缘检测、Hough变换、轮廓提取、种子填充、轮廓跟踪

    转自 http blog sina com cn s blog 6c083cdd0100nm4s html 7 1 边沿检测 我们给出一个模板 和一幅图象 不难发现原图中左边暗 右边亮 中间存在着一条明显的边界 进行模板操作后的结果如下 可

  • 关于Could not dlopen library和Cannot dlopen some GPU libraries等问题的解决建议

    在使用服务器的tensorflow1 14时 发现GPU内存占用很低 才100多M 而且GPU利用率为0 这根本没用GPU跑啊 回过头看编译输出的报告 出现了类似于 Could not dlopen library libcufft so

  • 进入Docker容器内部

    Docker容器运行起来以后 要想进入容器内部可以先通过docker ps命令查看 当前运行的容器信息 再通过 docker exec it ec3d30bff042 命令 其中ec3d30bff042为容器ID eg docker exe

  • 题解 . 洛谷题单之动态规划的引入

    前置知识 数字三角形问题 动态规划之数字三角形模型 如何何何的博客 CSDN博客 01背包问题 动态规划之01背包模型 如何何何的博客 CSDN博客 完全背包问题 动态规划之完全背包模型 如何何何的博客 CSDN博客 多重背包问题 动态规划

热门标签