c++11/c++98动态规划入门第5课,经典DP问题 --- 区间

有一排N个数,你和小明2个人玩游戏,每个人轮流从2端取数,每次可以从左或右取,不能从中间取。你取的所有的数的和是你的得分,小明取的所有的数的和是小明的得分。如果你先取,你最多比小明多得多少分?
输入格式
第一行:一个整数n,范围在[0, 100]。
第二行:n个整数,每个数范围在[1, 10000]。
输出格式
小明足够聪明时,你最多多得的分数。
输入/输出例子1
输入:
4
3 2 9 1
输出:
9
样例解释:
第1轮你取3;
第2轮他取2;
第3轮你取9;
第4轮他取1;
(3+9)-(2+1) = 9
样例解释
无
代码:
#include<bits/stdc++.h>
using namespace std;
int n,f[105][105],a[105],ans;
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i],f[i][i]=a[i];for(int i=1;i<=n;i++)for(int j=1;j+i<=n;j++)f[j][j+i]=max(-f[j+1][j+i]+a[j],-f[j][i+j-1]+a[i+j]); cout<<f[1][n];return 0;
}

有n个数字(0到99)排成一行,每一次可以将相邻的两个数字相加并对100取模(即除以100的余数),将结果取代之前的两个数,一次操作的花费为两个数字相乘。经过n-1次操作后剩下一个数,问剩下一个数时总花费的最小值。
输入格式
有若干组数据,每组数据第一行为一个正整数n(n<=100)表示数字的个数。
第二行为n个正整数(0到99)
输出格式
每组数据对应的最小花费。
输入/输出例子1
输入:
2
18 19
3
40 60 20
输出:
342
2400
样例解释
对于第二组数据有两种方案:
1、 先将(40和60)相加得0,再将0 和20相加得20,总花费为40*60+0*20=2400
2、 先将(60和20)相加得80,再将40和80相加得20,总花费为60*20+40*80=4400
显然第一种方案较好。
样例解释
无
代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[105],f[105][105],d[105];
int main(){while(scanf("%d",&n)!=EOF){for(int i = 0;i <= 105;i++){for(int j = 1;j <= 105;j++)f[i][j] = 1250000;}for(int i = 1;i <= 105;i++){d[i] = 0;}for(int i = 1;i <= n;i++){cin>>a[i];d[i] = d[i-1]+a[i];f[i][i] = 0;}for(int i = 2;i <= n;i++)for(int j = i;j <= n;j++){int lt = j-i+1;for(int k = lt;k < j;k++){int x = (d[k]-d[lt-1])%100;int y = (d[j]-d[k])%100;f[lt][j]=min(f[lt][j],f[lt][k]+f[k+1][j]+x*y);}}cout<<f[1][n]<<endl;}return 0;
} - 测试
为了挽救灾区同胞的生命,心系灾区同胞的你准备自己采购一些粮食支援灾区,现在假设你一共有资金n元,而市场有m种大米,每种大米都是袋装产品,其价格不等,并且只能整袋购买。请问:你用有限的资金最多能采购多少公斤粮食呢?
输入格式
输入数据首先包含一个正整数C,表示有C(C<=10)组测试数据,每组测试数据的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类,然后是m行数据,每行包含3个数p,h和c(1<=p<=20,1<=h<=200,1<=c<=20),分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。
输出格式
对于每组测试数据,请输出能够购买大米的最多重量,你可以假设经费买不光所有的大米,并且经费你可以不用完。每个数据的输出占一行。
输入/输出例子1
输入:
1
8 2
2 100 4
4 100 2
输出:
400
样例解释
无
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105],b[105],c[105];
int dp[105];
int n,m;
int main()
{int C;scanf("%d",&C);while(C--){memset(dp, 0, sizeof(dp));scanf("%d %d",&n,&m);for(int i=0; i<m; i++){scanf("%d %d %d",&a[i],&b[i],&c[i]);}for(int i=0; i<m; i++){for(int j=1; j<=c[i]; j++){for(int k=n; k>=a[i]*j; k--){dp[k]=max(dp[k-a[i]]+b[i], dp[k]);}}}printf("%d\n",dp[n]);}return 0;
} 有N张光盘,每张光盘有一个价钱,现在要从N张光盘中买M张,预算为L,每张光盘有一个快乐值,要求在不超过预算并且恰好买M张,使得快乐值总和最大。
输入格式
第一行为一个正整数T(1<=T<=5)表示测试数据个数
每组测试数据第一行为三个正整数N(N<=100),M(M<=N),L(L<=1000)
接下来的N行每行有两个正整数,分别是光盘的价钱与快乐值。
输出格式
每组数据对应的最大快乐值总和(保证小于2^31)。若无解则输出0.
输入/输出例子1
输入:
1
3 2 10
11 100
1 2
9 1
输出:
3
样例解释
无
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 1010;
const int INF = 1 << 31;
struct Movie
{int t,v;
};
Movie movie[MAXN];
int dp[MAXN][MAXN];
int n,m,l;
int main()
{int T;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&l);for(int i = 1;i <= m;i++)for(int j = 0;j <= l;j++)dp[j][i] = -INF;for(int j = 0;j <= l;j++)dp[j][0] = 0;for(int i = 1;i <= n;i++)scanf("%d%d",&movie[i].t,&movie[i].v);for(int i = 1;i <= n;i++)for(int j = l;j >= movie[i].t;j--)for(int k = m;k >= 1;k--)dp[j][k] = max(dp[j][k],dp[j-movie[i].t][k-1]+movie[i].v);int ans = 0;for(int i = 1;i <= l;i++)if(dp[i][m] > ans)ans = dp[i][m];printf("%d\n",ans);}return 0;
} 总结:
状态:线性DP --?-- 区间DP
阶段:长度
阶段的方向:2种 ------ 取决于“子问题”
相关文章:
c++11/c++98动态规划入门第5课,经典DP问题 --- 区间
第1题 取数问题 查看测评数据信息 有一排N个数,你和小明2个人玩游戏,每个人轮流从2端取数,每次可以从左或右取,不能从中间取。你取的所有的数的和是你的得分,小明取的所有的数的和是小明的得分。如果你先取&#x…...
vue中重新获取数据导致页面加长,要求在页面更新之后浏览器滚动条滚动到之前浏览记录的位置。以及获取当前页面中是哪个元素产生滚动条的方法。
目前的页面样式为: 代码是: <section id"detailSection"><el-tableref"multipleTable":data"logDetailList"style"width: 650px;margin:20px auto;"id"dialogDetail":show-header"fals…...
【深度学习】日常笔记14
对神经网络模型参数的初始化方案对保持数值稳定性有很重要的作用。初始化⽅案的选择可以与⾮线性激活函数的选择有趣的结合在⼀起。 突然有感触:做习题和模拟考研就分别是训练集和验证集,考研不就是最后的测试集() p168的↓的解释…...
[JAVAee]synchronized关键字
目录 1.synchronized的特性 ①互斥性 ②可重入性 2.synchronized的使用示例 ①修饰普通方法 ②修饰静态方法 ③修饰代码块 1.synchronized的特性 ①互斥性 互斥性,就像是给门上锁了一样. 当A线程使用了被synchronized修饰的代码块并对其上锁,其他线程(B线程,C线程)想要使…...
Unity游戏源码分享-3d机器人推箱子游戏
Unity游戏源码分享-3d机器人推箱子游戏 一个非常意思的3D游戏 工程地址:https://download.csdn.net/download/Highning0007/88098014...
SAAS部署模式
SAAS(Software as a Service)顾名思义,软件即服务的产品。 常见部署模式: 公有云:SAAS产品部署在公有云平台上,由SAAS提供商管理整个基础架构和应用程序。客户通过互联网访问和使用SAAS产品,无…...
11、PHP面向对象1
1、PHP的面向对象与其他语言类似,但也有不同。 PHP访问成员变量时,需要用“->”,而不能用“.”,访问成员函数时,需要用“->”,而不能用“.”。操作符“::”可以在没有任何声明实例的情况下访问类中的…...
实训笔记7.25
实训笔记7.25 7.25笔记一、MapReduce的特殊使用场景1.1 通过MapReduce程序实现多文件Join操作1.1.1 通过在Reduce端实现join操作1.1.2 通过在Map端实现join操作 1.2 MapReduce中的计数器的使用1.2.1 计数器使用两种方式 1.3 MapReduce实现数据清洗 二、MapReduce的OutputFormat…...
全方位对比 Postgres 和 MongoDB (2023 版)
本文为「数据库全方位对比系列」第二篇,该系列的首部作品为「全方位对比 Postgres 和 MySQL (2023 版)」 为何对比 Postgres 和 MongoDB 根据 2023 年 Stack Overflow 调研,Postgres 已经成为最受欢迎和渴望的数据库了。 MongoDB 曾连续 4 年 (2017 - …...
本地部署中文LLaMA模型实战教程,民间羊驼模型
羊驼实战系列索引 博文1:本地部署中文LLaMA模型实战教程,民间羊驼模型(本博客) 博文2:本地训练中文LLaMA模型实战教程,民间羊驼模型 博文3:精调训练中文LLaMA模型实战教程,民间羊驼模型 简介 LLaMA大部分是英文语料训练的,讲中文能力很弱。如果我们想微调训练自己的…...
全志F1C200S嵌入式驱动开发(spi-nor image制作)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 一般soc系统里面添加spi-nor flash芯片,特别是对linux soc来说,都是把它当成文件系统来使用的。spi-nor flash和spi-nand flash相比,虽然空间小了点,但是胜在稳定,这是很多工业…...
JSON格式Python,Java,PHP等封装图片识别商品数据API方法
淘宝是一个网上购物平台,售卖各类商品,包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取淘宝天猫图片识别商品数据,您可以通过开放平台的接口或者直接访问淘宝天猫商城的网页来获取图片识别商品数据。以下是两种常用方法的介绍&#…...
Vue应用案例
项目一:记事本 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8" /><title>title</title></head> <body><div id"app"><h2 >记事本</h2><input …...
GPT-3.5:ChatGPT的奇妙之处和革命性进步
🌷🍁 博主 libin9iOak带您 Go to New World.✨🍁 🦄 个人主页——libin9iOak的博客🎐 🐳 《面试题大全》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~ἳ…...
【Hadoop 01】简介
目录 1 Hadoop 简介 2 下载并配置Hadoop 2.1 修改/etc/profile 2.2 修改hadoop-env.sh 2.3 修改core-site.xml 2.4 修改hdfs-site.xml 2.5 修改mapred-site.xml 2.6 修改yarn-site.xml 2.7 修改workers 2.8 修改start-dfs.sh、stop-dfs.sh 2.9 修改start-yarn.sh、s…...
【C++】开源:跨平台轻量日志库easyloggingpp
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍跨平台轻量日志库easyloggingpp。 无专精则不能成,无涉猎则不能通。。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下&am…...
spring-websocket在SpringBoot(包含SpringSecurity)项目中的导入
✅作者简介:大家好,我是 Meteors., 向往着更加简洁高效的代码写法与编程方式,持续分享Java技术内容。 🍎个人主页:Meteors.的博客 🥭本文内容:spring-websocket在SpringBoot(包含SpringSecurity…...
SpringBoot + Vue前后端分离项目实战 || 六:Jwt加密整合配置
文章目录 回顾添加依赖Jwt依赖Jwt配置定义Jwt拦截器注册Jwt拦截器,配置需要验证token的URL 测试Jwt修改登录等逻辑 回顾 在之前的系统中,我们利用UUID配合Redis以达到角色登录的功能。 当前整个系统存在一个问题:人为修改token值后…...
WPF 如何设置全局的订阅发布事件
文章目录 前言代码逻辑修改 总结 前言 我们需要一个全局事件订阅发布功能,实现页面通讯。使两个毫无关系的页面通过一个中间量进行通讯。 代码 IEventAggregator:消息订阅集合 这个是Prism提供的消息订阅功能。使用如下 设置订阅类型,即…...
STM32 USB使用记录:HID类设备(前篇)
文章目录 目的基础说明HID类演示代码分析总结 目的 USB是目前最流行的接口,现在很多个人用的电子设备也都是USB设备。目前大多数单片机都有USB接口,使用USB接口作为HID类设备来使用是非常常用的,比如USB鼠标、键盘都是这一类。这篇文章将简单…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
