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

蓝桥杯备赛-精卫填海-DP

精卫终于快把东海填平了!只剩下了最后的一小片区域了。同时,西山上的木石也已经不多了。精卫能把东海填平吗?
事实上,东海未填平的区域还需要至少体积为 v 的木石才可以填平,而西山上的木石还剩下 n 块,每块的体积和把它衔到东海需要的体力分别为 k 和 m。精卫已经填海填了这么长时间了,她也很累了,她还剩下的体力为 c。

输入格式

输入文件的第一行是三个整数:v,n,c。从第二行到第 n+1 行分别为每块木石的体积和把它衔到东海需要的体力。

输出格式

输出文件只有一行,如果精卫能把东海填平,则输出她把东海填平后剩下的最大的体力,否则输出 Impossible(不带引号)。

输入输出样例

输入 

100 2 10
50 5
50 5

输出 

0

输入 

10 2 1
50 5
10 2

输出 

Impossible

说明/提示

数据范围及约定

  • 对于 20% 的数据,0<n≤50;
  • 对于 50% 的数据,0<n≤1000;
  • 对于 100% 的数据,0<n≤104,所有读入的数均属于 [0,104],最后答案不大于 c。
//精卫填海,8/10,2个超内存
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int main(){int v, n, c;cin >> v >> n >> c;//需要的体积,石头的数量,目前的体力值int k[100000];//体积int m[100000];//体力//或//vector<int> k(n + 1); // 体积//vector<int> m(n + 1); // 体力for (int i = 1; i <= n; i++){cin >> k[i] >> m[i];}vector<vector<int>> a(n + 1,vector<int>(v+1,0));//用i个石头填满j体积,需要的最少体力//必要:初始化一个很大的数表示不可能,用零块填满是不可能的,所有初始化最大。下面条件判断用的是min,如果不初始化最大,那么后面一直都是for (int i = 0; i < v + 1; i++)a[0][i] = 100000;//不必要:a[i][0]是0或100000不影响结果/*for (int i = 0; i < n + 1; i++)a[i][0] = 100000;*/for (int i = 1; i <= n; i++) {for (int j = 1; j <= v; j++) {//动态规划的核心:保持j的不变if (k[i]>=j) //一个石头就能填满{a[i][j] = min(a[i - 1][j], m[i]);//不放、只放一个、全放(舍)}else //一个石头填不满{a[i][j] = min(a[i - 1][j - k[i]]+m[i], a[i - 1][j]);//放、不放}}}if (a[n][v]>c)cout << "Impossible";elsecout << c-a[n][v];//注意用c-,不要忘记了return 0;
}

相关文章:

蓝桥杯备赛-精卫填海-DP

精卫终于快把东海填平了&#xff01;只剩下了最后的一小片区域了。同时&#xff0c;西山上的木石也已经不多了。精卫能把东海填平吗&#xff1f; 事实上&#xff0c;东海未填平的区域还需要至少体积为 v 的木石才可以填平&#xff0c;而西山上的木石还剩下 n 块&#xff0c;每块…...

Windows10配置C++版本的Kafka,并进行发布和订阅测试

配置的环境为&#xff1a;Release x64下的环境 完整项目&#xff1a;https://gitee.com/jiajingong/kafka-publisher 1、首先下载相应的库文件&#xff08;.lib&#xff0c;.dll&#xff09; 参考链接&#xff1a; GitHub - eStreamSoftware/delphi-kafka GitHub - cloade…...

vue3 下载文件 responseType-blob 或者 a标签

在 Vue 3 中&#xff0c;你可以使用 axios 或 fetch 来下载文件&#xff0c;并将 responseType 设置为 blob 以处理二进制数据。以下是一个使用 axios 的示例&#xff1a; 使用 axios 下载文件 首先&#xff0c;确保你已经安装了 axios&#xff1a; npm install axios然后在你…...

【Gin-Web】Bluebell社区项目梳理6:限流策略-漏桶与令牌桶

本文目录 一、限流二、漏桶三、令牌桶算法四、Gin框架中实现令牌桶限流 一、限流 限流又称为流量控制&#xff0c;也就是流控&#xff0c;通常是指限制到达系统的并发请求数。 限流虽然会影响部分用户的使用体验&#xff0c;但是能一定程度上保证系统的稳定性&#xff0c;不至…...

51单片机-AT24CXX存储器工作原理

1、AT24CXX存储器工作原理 1.1、特点&#xff1a; 与400KHz&#xff0c;I2C总线兼容1.8到6.0伏工作电压范围低功耗CMOS技术写保护功能当WP为高电平时进入写保护状态页写缓冲器自定时擦写周期100万次编程/擦除周期可保存数据100年8脚DIP SOIC或TSSOP封装温度范围商业级和工业级…...

突破性能极限:DeepSeek开源FlashMLA解码内核技术解析

引言&#xff1a;大模型时代的推理加速革命 在生成式AI大行其道的今天&#xff0c;如何提升大语言模型的推理效率已成为行业焦点。DeepSeek团队最新开源的FlashMLA项目凭借其惊人的性能表现引发关注——在H800 GPU上实现580 TFLOPS计算性能&#xff0c;这正是大模型推理优化的…...

点击修改按钮图片显示有问题

问题可能出在表单数据的初始化上。在 ave-form.vue 中&#xff0c;我们需要处理一下从后端返回的图片数据&#xff0c;因为它们可能是 JSON 字符串格式。 vue:src/views/tools/fake-strategy/components/ave-form.vue// ... existing code ...Watch(value)watchValue(v: any) …...

[AI]从零开始的树莓派运行DeepSeek模型教程

一、前言 在前面的教程中&#xff0c;教了大家如何在windows中使用llama.cpp来运行DeepSeek模型。根据前面的教程中&#xff0c;我们也了解到了&#xff0c;我们只需要编译好llama.cpp就可以运行DeepSeek以及类似的LLM模型。那么本次教程就来教大家如何使用树莓派来运行大模型。…...

2024-2025 学年广东省职业院校技能大赛 “信息安全管理与评估”赛项 技能测试试卷(二)

2024-2025 学年广东省职业院校技能大赛 “信息安全管理与评估”赛项 技能测试试卷&#xff08;二&#xff09; 第一部分&#xff1a;网络平台搭建与设备安全防护任务书第二部分&#xff1a;网络安全事件响应、数字取证调查、应用程序安全任务书任务 1&#xff1a;应急响应&…...

Open WebUI本地部署教程

文章目录 1、系统环境配置2、源码下载2.1 github源码地址下载 3、环境启动3.1 后端环境3.2 前端环境 4、问题4.1 浏览器跨域问题4.2 all-MiniLM-L6-v2模型文件下载失败问题4.3 单独部署backend启动报错问题 1、系统环境配置 操作系统&#xff1a;windows/linux/macos Python版…...

Missing required prop: “maxlength“

背景&#xff1a; 封装一个使用功能相同使用频率较高的input公共组件作为子组件&#xff0c;大多数长度要求为200&#xff0c;且实时显示统计子数&#xff0c;部分input有输入提示。 代码实现如下&#xff1a; <template><el-input v-model"inputValue" t…...

dify本地部署

安装docker。 在官网安装docker。 如果遇到wsl报错&#xff0c;就使用 wsl --updata 进行更新。如果问题解决&#xff0c;进入docker应该是如下界面&#xff1a; 克隆 在自己创建的文件内使用 git clone gitgithub.com:langgenius/dify.git 或 git clone https://github.com…...

python学习一

学习网络安全为什么要学python? 1、在实际的渗透测试过程中,面对复杂多变的网络环境,当常用工 具不能满足实际需求的时候,往往需要对现有工具进行扩展,或者 编写符合我们要求的工具、自动化脚本,这个时候就需要具备一定 的编程能力。 2、python是一门编程语言经常用它…...

git branch

文章目录 1.简介2.格式3.选项4.示例参考文献 1.简介 git branch 用于管理分支&#xff0c;包括查看、创建、删除、重命名和关联。 git branch 是 Git 版本控制系统中用于管理分支的命令。分支是 Git 的核心功能之一&#xff0c;允许开发者在同一个代码库中并行开发不同的功能…...

算法-图-数据结构(邻接矩阵)-BFS广度优先遍历

邻接矩阵广度优先遍历&#xff08;BFS&#xff09;是一种用于遍历或搜索图的算法&#xff0c;以下是具体介绍&#xff1a; 1. 基本概念 图是一种非线性的数据结构&#xff0c;由顶点和边组成&#xff0c;可分为无向图、有向图、加权图、无权图等。邻接矩阵是表示图的一种数…...

数学建模之数学模型—2:非线性规划

文章目录 非线性规划基本概念与结论凸集与凸函数极值条件无约束条件的极值判断条件有约束条件的极值判断条件 无约束非线性规划一维搜索算法步骤示例特点代码模板 最速下降法算法详细步骤 代码实现示例最优步长的求解 黄金分割法斐波那契法牛顿法阻尼牛顿法模式搜索法Powell方法…...

unity学习51:所有UI的父物体:canvas画布

目录 1 下载资源 1.1 在window / Asset store下下载一套免费的UI资源 1.2 下载&#xff0c;导入import 1.3 导入后在 project / Asset下面可以看到 2 画布canvas&#xff0c;UI的父物体 2.1 创建canvas 2.1.1 画布的下面是 event system是UI相关的事件系统 2.2 canvas…...

ctfshow做题笔记—栈溢出—pwn57~pwn60

目录 前言 一、pwn57&#xff08;先了解一下简单的64位shellcode吧&#xff09; 二、pwn58 三、pwn59&#xff08;64位 无限制&#xff09; 四、pwn60&#xff08;入门难度shellcode&#xff09; 前言 往前写了几道题&#xff0c;与shellcode有关&#xff0c;关于shellc…...

数据结构 1-2 线性表的链式存储-链表

1 原理 顺序表的缺点&#xff1a; 插入和删除移动大量元素数组的大小不好控制占用一大段连续的存储空间&#xff0c;造成很多碎片 链表规避了上述顺序表缺点 逻辑上相邻的两个元素在物理位置上不相邻 头结点 L&#xff1a;头指针 头指针&#xff1a;链表中第一个结点的存储…...

ArcGIS Pro进行坡度与坡向分析

在地理信息系统中&#xff0c;坡度分析是一项至关重要的空间分析方法&#xff0c;旨在精确计算地表或地形的坡度&#xff0c;为地形特征识别、土地资源规划、环境保护、灾害预警等领域提供科学依据。本文将详细介绍如何利用ArcGIS Pro这一强大的地理信息系统软件&#xff0c;进…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...