洛谷P1509找啊找啊找GF

题解:这题我们需要考虑两个因素 ,既要有钱,也需要有人品,但是呢,还想花最少得时间泡到最多的女生,那么这题我们就要用到以往的二维dp数组,但是真的是二维的吗?不,因为要考虑女生的数量以及时间,真正应该是三维的,因此,我们可以得到状态转移方程式,

当数量可以增加时,数量和时间都要相应增加,但是当人数不变时,只需要考虑最小时间,吟哦写出dp方程式

if(dp[j][k][0]<dp[j-rmb[i]][k-rp[i]][0]+1)
				{
					dp[j][k][0]=dp[j-rmb[i]][k-rp[i]][0]+1;
					dp[j][k][1]=dp[j-rmb[i]][k-rp[i]][1]+t[i];
				}
				if(dp[j][k][0]==dp[j-rmb[i]][k-rp[i]][0]+1)
				dp[j][k][1]=min(dp[j][k][1],dp[j-rmb[i]][k-rp[i]][1]+t[i]);

 AC代码:

#include<bits/stdc++.h>
using namespace std;

int n,m,r;
int rmb[105],rp[105],t[105];
int dp[105][105][2];
int rmax=0,tmax=0x3f3f3f3f;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&rmb[i],&rp[i],&t[i]);
	}
	scanf("%d%d",&m,&r);
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=rmb[i];j--)
		{
			for(int k=r;k>=rp[i];k--)
			{
				if(dp[j][k][0]<dp[j-rmb[i]][k-rp[i]][0]+1)
				{
					dp[j][k][0]=dp[j-rmb[i]][k-rp[i]][0]+1;
					dp[j][k][1]=dp[j-rmb[i]][k-rp[i]][1]+t[i];
				}
				if(dp[j][k][0]==dp[j-rmb[i]][k-rp[i]][0]+1)
				dp[j][k][1]=min(dp[j][k][1],dp[j-rmb[i]][k-rp[i]][1]+t[i]);
			}
		}
	}
	printf("%d",dp[m][r][1]);
	return 0;
}

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

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

相关文章

mitmproxy代理

文章目录 mitmproxy1. 网络代理2. 安装3. Https请求3.1 启动mitmproxy3.2 获取证书3.3 配置代理3.4 运行测试 4. 请求4.1 读取请求4.2 修改请求4.3 拦截请求 5. 响应5.1 读取响应5.2 修改响应 6. 案例&#xff1a;共享账号6.1 登录bilibili获取cookies6.2 在代理请求中设置cook…

116. 飞行员兄弟 刷题笔记

/* 二进制枚举 两个状态 1.将0-2^16-1 的二进制表示映射成 所有的方案 2.逐步检查该二进制数每一位 对该位与上1 如果成立则该改变改行该列的状态 写一个 get函数 将i j转化为当前二进制的位数 3. 检查所有的把手状态 是否都打开 */ 代码 #include<iostream> #i…

LeetCode 刷题 [C++] 第55题.跳跃游戏

题目描述 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 题目分析 题目中…

技术活也能轻松搞定!Xinstall一键完成Android多渠道打包

随着移动互联网的迅猛发展&#xff0c;Android应用市场呈现出百花齐放的态势。为了满足不同市场的需求&#xff0c;开发者们常常需要为同一个应用打包多个渠道版本。然而&#xff0c;传统的打包方式繁琐且耗时&#xff0c;让渠道运营人员苦不堪言。今天&#xff0c;我们就来聊聊…

线上历史馆藏系统 Java+SpringBoot+Vue+MySQL

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

(四)CarPlay集成开发之无线连接

上一篇写了CarPlay有线开发中的一些依赖&#xff0c;相比有线连接&#xff0c;无线连接的开发工作可能会比较简单一些, 主要的开发工作有如下内容 无线CarPlay连接开发 蓝牙协议栈扩展UUID配件端蓝牙CarPlay EIR扩展配件端蓝牙iAP2 EIR扩展苹果设备端蓝牙EIR扩展 hostapd添加IE…

Http基础之http协议、无状态协议、状态码、http报文、跨域-cors

Http基础 HTTP基础HTTP协议请求方法持久连接管线化 无状态协议使用Cookie状态管理 状态码1XX2XX OK200 OK204 NO Content206 Content-Range 3XX 重定向301302304307 4XX400401403404 5XX500503 HTTP报文请求报文响应报文通用首部字段Cache-ControlConnectionDate请求首部字段Ac…

【SpringBoot】测试单元使用多线程

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;SpringBoot ⛺️稳重求进&#xff0c;晒太阳 问题产生 今天学习了乐观锁&#xff0c;但在测试单元执行多线程的时候出现了问题&#xff0c;多线程并没有直接结果 在控制台没有任何输出…

Leetcode560. 和为 K 的子数组 -hot100

题目&#xff1a; 代码(首刷看解析 2024年3月2日&#xff09;&#xff1a; class Solution { public:int subarraySum(vector<int>& nums, int k) {// 前缀和 遍历int res 0;unordered_map<int, int> sumPre;int sum 0;// 关键&#xff1a;初始化sumPre[0]…

MyBatis 学习(七)之 缓存

目录 1 MyBatis 缓存介绍 2 一级缓存 3 二级缓存 3.1 二级缓存介绍 3.2 二级缓存配置 3.3 二级缓存测试 4 参考文档 1 MyBatis 缓存介绍 MyBatis 缓存是 MyBatis 中的一个重要特性&#xff0c;用于提高数据库查询的性能。MyBatis 提供了一级缓存和二级缓存两种类型的缓存…

计算机毕业设计分享-SSM课程题库管理系统 18655(赠送源码数据库)JAVA、PHP,node.js,C++、python,大屏数据可视化等

毕业设计&#xff08;论文&#xff09; SSM课程题库管理系统 学 院 专 业 班 级 学 号 学生姓名 指导教师 完成日期…

【.Net 使用阿里云OSS 存储文件】

一、使用NuGet安装【Aliyun.OSS.SDK】 注意&#xff1a;如果有多个项目&#xff0c;需要在具体使用的项目跟启动项目都安装同一版本的Aliyun.OSS.SDK 二、上传代码 using Aliyun.OSS; using System.IO; using System; using CadApplication.Service.Dto; using System.Net; us…

QT绘图

QPainter paintEvent是Qt中一个非常重要的函数&#xff0c;它是QWidget类的一个事件处理函数&#xff0c;用于处理小部件的绘制事件。当Qt认为小部件需要重绘时&#xff08;例如&#xff0c;窗口首次出现时&#xff0c;大小改变时&#xff0c;或者调用了小部件的update()方法时…

【硬件相关】IB网/以太网基础介绍及部署实践

文章目录 一、前言1、Infiniband网络1.1、网络类型1.2、网络拓扑1.3、硬件设备1.3.1、网卡1.3.2、连接线缆a、光模块b、线缆 1.3.4、交换机 2、Ethernet网络 二、部署实践&#xff08;以太网&#xff09;1、Intel E810-XXVDA21.1、网卡信息1.2、检查命令1.2、驱动编译 2、Mella…

SQLPro Studio:数据库管理的革命性工具 mac版

SQLPro Studio是一款强大的数据库管理和开发工具&#xff0c;它旨在提供高效、便捷和安全的数据库操作体验。无论是数据库管理员、开发人员还是数据分析师&#xff0c;SQLPro Studio都能满足他们在数据库管理、查询、设计和维护方面的需求。 SQLPro Studio mac版软件获取 首先…

低密度奇偶校验码LDPC(八)——QC-LDPC译码器FPGA设计概要

往期博文 低密度奇偶校验码LDPC&#xff08;一&#xff09;——概述_什么是gallager构造-CSDN博客 低密度奇偶校验码LDPC&#xff08;二&#xff09;——LDPC编码方法-CSDN博客 低密度奇偶校验码LDPC&#xff08;三&#xff09;——QC-LDPC码概述-CSDN博客 低密度奇偶校验码…

Python环境搭建:一站式指南

在当前AIGC技术蓬勃发展的背景下&#xff0c;Python作为人工智能领域最受青睐的编程语言之一&#xff0c;成为我们必须掌握的技能。因此&#xff0c;搭建一个适合自己的Python环境成为了每个Python开发者的首要任务。本文将为您提供一站式的Python环境搭建指南&#xff0c;帮助…

JVM(5)

垃圾回收相关 垃圾收集器 警告:纯八股文! 如果说上面我们讲的收集算法是内存回收的方法论,那么垃圾收集器就是内存回收的具体体现. 垃圾收集器的作用:垃圾收集器是为了保证程序能够正常,持久运行的一种技术,它是将程序中不用的死亡对象也就是垃圾对象进行清除,从而保证新的…

Godot自定义控件样式语法解析

前言 本篇原始文章写于2023年8月7日&#xff0c;存储在我的语雀文档中。但是语雀分享有诸多不便&#xff0c;为了让更多Godoter更轻松的搜到和看到&#xff0c;就转过来了。 这个项目我上传了Github&#xff0c;后续会贴上链接。 概述 Godot控件体系存在的问题之一就是样式无…

链表OJ刷题(二)

制作不易&#xff0c;三连支持一下呗&#xff01;&#xff01;&#xff01; 文章目录 前言一、链表的回文结构二、相交链表三、链表中倒数第k个节点四、环形链表Ⅰ和Ⅱ总结 前言 一、链表的回文结构 链表的回文结构_牛客题霸_牛客网 这里我们需要先了解一下什么叫做回文&#…