动态规划刷题(算法竞赛、蓝桥杯)--区间DP

1、题目链接:[NOI1995] 石子合并 - 洛谷

61c434cfab2847ab8a43353a310d84ac.png

#include <bits/stdc++.h>
using namespace std;
const int N=210;
int n,a[N],s[N];
int f[N][N];//存最小值 
int g[N][N];//存最大值 

int main(){
	memset(f,0x3f,sizeof f);//求最小初始化为无穷大 
	memset(g,-0x3f,sizeof g);//求最大初始化为无穷小 
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]),a[i+n]=a[i];
	}
	for(int i=1;i<2*n;i++){
		s[i]=s[i-1]+a[i];//求前缀和 
		g[i][i]=0;//同一堆价值为0 
		f[i][i]=0;
	}
	int minv=1e9,maxv=-1e9;
	for(int len=2;len<=n;len++){//枚举区间长度 
		for(int i=1,j;(j=len+i-1)<=2*n;i++){//枚举左右端点 
			for(int k=i;k<j;k++){//枚举区间的分割点 
				f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
				g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
			}
			minv=min(minv,f[i][i+n-1]);//便利在2*n内所有长度为n的区间 
			maxv=max(maxv,g[i][i+n-1]);
		}
	}
	printf("%d\n%d\n",minv,maxv); 
	return 0;
}

2、题目链接:[NOIP2006 提高组] 能量项链 - 洛谷

6b50ab9a0b9740c9a22d987ef81f7a06.png

4d8ce9f2c0274f8a9d13f685d4ba47bc.png

#include <bits/stdc++.h>
using namespace std;
const int N=210;
int n,a[N];//a[i]为第i颗珠子的头标记
int f[N][N];//f[i][j] 表示合并[i,j]得到的最大能量

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i],a[i+n]=a[i];
	}
	for(int len=3;len<=n+1;len++){//枚举区间长度 
		for(int i=1,j;(j=i+len-1)<=2*n;i++){//枚举左右端点 
			for(int k=i+1;k<j;k++){//枚举区间的分割点 
				f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
			}
		}
	}
	int res=0;
	for(int i=1;i<=n;i++){
		res=max(res,f[i][i+n]);
	}
	cout<<res<<endl;
	return 0;
}

3、题目链接:[USACO16OPEN] 248 G - 洛谷

2ee8e3fe11214deb92fd12269910a6f8.png

#include <bits/stdc++.h>
using namespace std;
const int N=250;
int f[N][N];
int a[N];
int n,res;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i][i]=a[i];//自身的值 
		res=max(res,f[i][i]);//取最大值 
	}
	for(int len=2;len<=n;len++){//枚举长度 
		for(int i=1,j;(j=i+len-1)<=n;i++){//枚举左右端点 
			for(int k=i;k<j;k++){//枚举分割点 
				if(f[i][k]==f[k+1][j]&&f[i][k]){//相邻两个数相等且不为0 
					f[i][j]=max(f[i][j],f[i][k]+1);
					res=max(res,f[i][j]);
				}
			}
		}
	}
	cout<<res;
	
	return 0;
}

 

 

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

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

相关文章

智慧能耗预付费系统解决方案——用户侧能源计量及收费

安科瑞电气股份有限公司 祁洁 15000363176 一、方案组织架构 二、方案特点 &#xff08;1&#xff09;多样组网&#xff0c;多样设备接入&#xff0c;多样部署&#xff1b; &#xff08;2&#xff09;集团管理、项目分级、分层拓扑&#xff1b; &#xff08;3&#xff09…

ImageView显示叠加图

imageView显示叠加图&#xff1a;背景是绿色&#xff0c;中间为add图标 <ImageViewandroid:id"id/iv_add_food"android:layout_width"80dp"android:layout_height"80dp"android:layout_below"id/iv_filter"android:layout_marginTo…

C语言 03 VSCode开发

安装好 C 语言的开发环境后&#xff0c;就需要创建项目进行开发了。 使用 IDE&#xff08;集成开发环境&#xff09;进行开发了。 C 语言的开发工具很多&#xff0c;现在主流的有 Clion、Visual Studio、VSCode。 这里以 VSCode 作为演示。 创建项目 安装 VSCode。 推荐直接在…

抖音-引流私域转化模式1.0现场视频,从抖音源源不断把人加到私域,

抖音-引流私域转化模式1.0现场视频&#xff0c;从抖音源源不断把人加到私域&#xff0c;让加到私域的粉丝买单 抖音-引流私域转化模式1.0现场视频&#xff0c;从抖音源源不断把人加到私域 - 百创网-源码交易平台_网站源码_商城源码_小程序源码 课程内容&#xff1a; 01.第一…

yolov8草莓及病害检测项目开发(python开发,带有训练模型,可以重新训练,并有Pyqt5界面可视化)

本次检测系统&#xff0c;可以通过图片、视频或摄像头三种形式检测&#xff0c;检测出开花、结果、熟果、草莓叶子健康、叶子缺钙、灰叶斑病等八大类别。基于最新的YOLO-v8训练的草莓检测模型和完整的python代码以及草莓的训练数据&#xff0c;下载后即可运行&#xff0c;输出检…

Centos7 安装GitLab

安装环境: 虚拟机:Centos7 最小安装 4核8G 下载GitLab 本次实验下载的是 gitlab-ce-14.1.0-ce.0.el7.x86_64.rpm 官网截图 清华源截图 安装包下载地址(官网;下载CE版本,EE是收费版本):https://packages.gitlab.com/gitlab/gitlab-ce国内镜像源下载地址(清华源):htt…

websocket实践

文章目录 背景WebSocket API使用场景优点 实例步骤 1: 设置 WebSocket 服务器步骤 2: 创建客户端 HTML 页面步骤 3: 测试 WebSocket 通信注意事项实际操作 参考资料 WebSocket 是一种在单个 TCP 连接上进行全双工通信的协议。它使得浏览器和服务器只需建立一个连接&#xff0c;…

HarmonyOS实战开发-AccessibilityExtensionAbility示例。

介绍 本示例展示了AccessibilityExtensionAbility的简单应用&#xff0c;使用多个辅助功能接口实现了一些快捷的交互方式。 效果预览 使用说明 1.在启动无障碍扩展服务前&#xff0c;需退出当前应用保证界面节点正常生成&#xff1b; 2.启动关闭无障碍扩展服务可参考Access…

阿里云服务器的主要用途是什么?

阿里云服务器可以干嘛&#xff1f;能干啥你还不知道么&#xff01;简单来讲可用来搭建网站、个人博客、企业官网、论坛、电子商务、AI、LLM大语言模型、测试环境等&#xff0c;阿里云百科aliyunbaike.com整理阿里云服务器的用途&#xff1a; 阿里云服务器活动 aliyunbaike.com…

【分治算法】大整数乘法Python实现

文章目录 [toc]问题描述基础算法时间复杂性 优化算法时间复杂性 Python实现 个人主页&#xff1a;丷从心. 系列专栏&#xff1a;Python基础 学习指南&#xff1a;Python学习指南 问题描述 设 X X X和 Y Y Y都是 n n n位二进制整数&#xff0c;计算它们的乘积 X Y XY XY 基础…

猫冻干可以每天吃吗?5大优选品牌脆弱肠胃闭眼入

近年来&#xff0c;冻干猫粮作为备受追捧的高品质猫粮&#xff0c;吸引了越来越多养猫人的关注&#xff0c;对于像我这样的养猫达人来说&#xff0c;早已尝试并认可了冻干喂养。但对于新手来说&#xff0c;他们可能会感到困惑&#xff1a;冻干到底是什么&#xff1f;猫冻干可以…

腾讯电商运营起来竟然这么简单!视频号小店操作玩法一文详解!

大家好&#xff0c;我是电商小布。 在新型电商玩法的兴起下&#xff0c;很多的平台都在电商行业内分到了一杯羹。 腾讯自然也就坐不住了&#xff0c;背靠自身的视频号平台&#xff0c;推出了视频号小店这个项目。 有很多的小伙伴想要趁着这个初期阶段&#xff0c;来加入到其…

CentOS部署Apache Superset大数据可视化BI分析工具并实现无公网IP远程访问

文章目录 前言1. 使用Docker部署Apache Superset1.1 第一步安装docker 、docker compose1.2 克隆superset代码到本地并使用docker compose启动 2. 安装cpolar内网穿透&#xff0c;实现公网访问3. 设置固定连接公网地址 前言 Superset是一款由中国知名科技公司开源的“现代化的…

cesium 地图旋转 整个场景旋转 开场动画

设置camera旋转能实现整个场景的旋转&#xff0c;多用于开场动画 开始旋转 function onTickCallback() {viewer.scene.camera.rotate(Cesium.Cartesian3.UNIT_Z, -0.02);}viewer.clock.onTick.addEventListener(onTickCallback); 停止旋转 viewer.clock.onTick.removeEvent…

掼蛋八大定律

1、首引定律 沟通是掼蛋的灵魂&#xff0c;原则上前三手牌都需要沟通。第一手牌&#xff0c;沟通牌力强弱&#xff1b;第二手牌沟通上游概率&#xff1b;第三手牌沟通双下可能。首引定律有几个公式&#xff1a;&#xff08;1&#xff09;首引小单牌示弱&#xff1b;&#xff0…

CCIE-10-IPv6-TS

目录 实验条件网络拓朴 环境配置开始Troubleshooting问题1. R25和R22邻居关系没有建立问题2. 去往R25网络的下一跳地址不存在、不可用问题3. 去往目标网络的下一跳地址不存在、不可用 实验条件 网络拓朴 环境配置 在我的资源里可以下载&#xff08;就在这篇文章的开头也可以下…

FDFB with smaller noise

参考文献&#xff1a; [CZB22] Clet P E, Zuber M, Boudguiga A, et al. Putting up the swiss army knife of homomorphic calculations by means of TFHE functional bootstrapping[J]. Cryptology ePrint Archive, 2022.[MHW23] Ma S, Huang T, Wang A, et al. Fast and ac…

富家千金私奔破产小子:卓文君与渣男司马相如

当戏文里爱唱的千金大小姐爱上穷小子成为现实&#xff0c;是否会像电视剧里的一样美好。 司马相如与卓文君的爱情故事就上演了这样的戏码&#xff0c;他所作的一首《凤求凰》更是被传成佳话&#xff0c;千古流传。 让大多数人误以为他们伉俪情深&#xff0c;可是事情的真相却…

低代码平台种草推荐

告别繁琐&#xff0c;拥抱未来&#xff01;只需简单拖拽&#xff0c;Vue代码即刻生成&#xff0c;一键下载&#xff0c;轻松上手。我们的低代码平台&#xff0c;不仅高效便捷&#xff0c;更完全开源&#xff0c;让你自由探索编程的无限可能&#xff01; 下载网址&#xff1a;ht…