杭电2159-FATE (二维背包运用+详细解释)

2024-05-11 03:38

本文主要是介绍杭电2159-FATE (二维背包运用+详细解释),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

FATE

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5700    Accepted Submission(s): 2609


Problem Description
最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗?
 

Input
输入数据有多组,对于每组数据第一行输入n,m,k,s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值,保留的忍耐度,怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a,b(0 < a,b < 20);分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)
 

Output
输出升完这级还能保留的最大忍耐度,如果无法升完这级输出-1。
 

Sample Input
  
10 10 1 10 1 1 10 10 1 9 1 1 9 10 2 10 1 1 2 2
 

Sample Output
  
0 -1 1
二维背包题,AC代码+详细解释:
#include<iostream>//二维背包
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
const int MAX=1001;
int DP[MAX][MAX];//用来存储杀了i个同怪物和用了j忍耐度是的最大经验值
using namespace std;
typedef struct Monster
{int exe;//怪物的经验值int endur;//消耗的忍耐度
}monster;
monster ss[MAX];
bool Max(int x,int y)
{if(x>y)return true;elsereturn false;
}
int main()
{int n,m,k,s;int i,j,a,b,Min;while(cin>>n>>m>>k>>s){memset(DP,0,sizeof(DP));for(i=1;i<=k;i++){cin>>ss[i].exe>>ss[i].endur;}for(i=1;i<=k;i++)//对不同物种遍历一遍{for(j=1;j<=s;j++)//杀了j个怪物{for(int k=ss[i].endur;k<=m;k++)//指用掉的忍耐度为k{if(Max(DP[j-1][k-ss[i].endur]+ss[i].exe,DP[j][k]))//判断如果杀了这一只怪物比不杀可以是否得到更大的经验值DP[j][k]=DP[j-1][k-ss[i].endur]+ss[i].exe;}}}if(DP[s][m]<n)//如果经验值小于所需的经验值则输出-1cout<<"-1"<<endl;else{Min=m;//最大要赋给m,因为要找出一种情况是可以升级成功并且用的忍耐度最小for(i=1;i<=s;i++){for(j=0;j<=m;j++){if(DP[i][j]>=n&&j<Min)//如果DP[i][j]>=n说明杀了i只怪物用了j忍耐度时可以升级成功,则Min=j;Min=j;}}cout<<m-Min<<endl;//输出剩余的忍耐值}}return 0;
}


 

这篇关于杭电2159-FATE (二维背包运用+详细解释)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/978399

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Centos环境下Tomcat虚拟主机配置详细教程

《Centos环境下Tomcat虚拟主机配置详细教程》这篇文章主要讲的是在CentOS系统上,如何一步步配置Tomcat的虚拟主机,内容很简单,从目录准备到配置文件修改,再到重启和测试,手把手带你搞定... 目录1. 准备虚拟主机的目录和内容创建目录添加测试文件2. 修改 Tomcat 的 server.X

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring Boot拦截器Interceptor与过滤器Filter详细教程(示例详解)

《SpringBoot拦截器Interceptor与过滤器Filter详细教程(示例详解)》本文详细介绍了SpringBoot中的拦截器(Interceptor)和过滤器(Filter),包括它们的... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)详细教程1. 概述1

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》:本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务,并使用ngrok暴露到公网。#sql_tools.pyfrom