首页 > 其他分享 >杭电OJ-2159-FATE踩坑记录

杭电OJ-2159-FATE踩坑记录

时间：2023-06-19 16:34:50浏览次数：50  
标签：10 OJ FATE xhd int MAX 杭电 flag 忍耐

杭电OJ-2159-FATE 解题记录

目录

题目描述

FATE

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

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

数据定义

#define MAX 101				//题目规定最大为100，从1号单元开始用则需要101个单元
//全局变量
int f[MAX][MAX][MAX];		//一般解法，用三维数组保存所有数据
int f[MAX][MAX];			//优化解法，用二维数组，当前层的数据覆盖上一层的数据
int a[MAX];
int b[MAX];

//main函数局部变量
int n, k;				//n还需的经验值，k怪的种数，
int m, s;				//m保留的忍耐度，s最多的杀怪数
int flag = 1;			//flag=1表示还没找到可升级的位置
int leftpatient = -1;	//表示剩余的忍耐度

递推公式

\[f[i][j][x] = max(f[i - 1][j][x], f[i][j - b[i]][x - 1] + a[i]); \]

  • \(i\) 代表考虑前 i 个怪
  • \(j\) 代表忍耐度
  • \(x\) 代表当前考虑的最多杀怪数
  • \(f[i][j][k]\) 表示只考虑前 i 个怪，在忍耐度为 j ，最多杀怪数为 x 的情况下可以得到的最大经验值
  • \(f[i - 1][j][x]\) 表示不打当前种类的怪，则【只考虑前 i 个怪得到的最大经验值】与【只考虑前 i-1 个怪得到的最大经验值】相同
  • \(f[i][j - b[i]][x - 1] + a[i]\) 表示打当前种类的怪，即打的当前怪的数量 >= 1
    • 至少打一只，能得到 a[i] 的经验
    • 有可能不止一只，则仍需考虑当前种类，即第一维仍然为 [i]
    • 但由于已经考虑了一只，因此 \(j\Leftarrow j-b[i],\ x\Leftarrow x-1\)

一般解法——用三维数组保存所有数据

核心代码如下：

//=========================================================================================================
//一般解法：三维数组，存放所有可能的解
for (int i = 1; i <= k; i++)			//第i个怪，共k个怪
    for (int j = 1; j <= m; j++)		//当前总忍耐度为j，最大忍耐度为m
        for (int x = 1; x <= s; x++)	//当前最多杀怪数为x
        {
            if (j < b[i])
                f[i][j][x] = f[i - 1][j][x];
            else
                f[i][j][x] = max(f[i - 1][j][x], f[i][j - b[i]][x - 1] + a[i]);
            if (i==k && flag && f[i][j][x] >= n)	//第一次达到升级经验
            {
                leftpatience = m - j;
                flag = 0;
            }
        }
//cout << f[k][m][s] << endl;	//最大能获取的经验
//=========================================================================================================
  • 坑1：最内层循环中的判断条件 i=k
    • 原因：需要保证所有怪都已经纳入考虑范围后再选择最小的 j ，否则可能 j 会偏大

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 101				//题目规定最大为100，从1号单元开始用则需要101个单元
using namespace std;

int f[MAX][MAX][MAX];		//一般解法，用三维数组保存所有数据
int a[MAX];
int b[MAX];

int main() {
	int n, k;			//n还需的经验值，k怪的种数，
	int m, s;			//m保留的忍耐度，s最多的杀怪数
	int flag = 1;			//flag=1表示还没找到可升级的位置
	int leftpatience = -1;	//表示剩余的忍耐度

	while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
		leftpatience = -1;	//重置leftpatience
		flag = 1;			//重置flag
		for (int i = 1; i <= k; i++)
			cin >> a[i] >> b[i];
		//=========================================================================================================
		//一般解法：三维数组，存放所有可能的解
		for (int i = 1; i <= k; i++)			//第i个怪，共k个怪
			for (int j = 1; j <= m; j++)		//当前总忍耐度为j，最大忍耐度为m
				for (int x = 1; x <= s; x++)	//当前最多杀怪数为x
				{
					if (j < b[i])
						f[i][j][x] = f[i - 1][j][x];
					else
						f[i][j][x] = max(f[i - 1][j][x], f[i][j - b[i]][x - 1] + a[i]);
					if (i==k && flag && f[i][j][x] >= n)	//第一次达到升级经验
					{
						leftpatience = m - j;
						flag = 0;
					}
				}
		//=========================================================================================================

		cout << leftpatience << endl << endl;	//升级时剩余的忍耐度
	}
	return 0;
}

优化解法——用二维数组，当前层的数据覆盖上一层的数据

核心代码如下：

//优化解法：二维数组，存放所有可能的解
memset(f, 0, sizeof(f));	//由于二维数组需要循环利用，故【务必】在处理下一组数据前把数组复位，否则在执行max函数时会受影响
for (int i = 1; i <= k; i++)			//第i个怪，共k个怪
    for (int j = 1; j <= m; j++)		//当前总忍耐度为j，最大忍耐度为m
        for (int x = 1; x <= s; x++)	//当前最多杀怪数为x
        {
            if (j >= b[i])
                f[j][x] = max(f[j][x], f[j - b[i]][x - 1] + a[i]);
            if (i == k && flag && f[j][x] >= n)	//第一次达到升级经验
            {
                leftpatience = m - j;
                flag = 0;
            }
        }
  • 坑1：memset(f, 0, sizeof(f));
    • 原因：由于OJ会输入多组数据，因此每组数据输入前要把数组清零，防止上一组的结果对当前组产生影响（如max函数）
  • 坑2：... for(int j = 2; ....) ... if (j >= b[i]) f[j][x] = ...
    • 如果不需要求 leftpatience ，则可以用如下代码解二维完全背包：
      for (int i = 1; i <= k; i++)			//第i个怪，共k个怪
    for (int j = b[i]; j <= m; j++)		//当前总忍耐度为j，最大忍耐度为m
        for (int x = 1; x <= s; x++)	//当前最多杀怪数为x
                f[j][x] = max(f[j][x], f[j - b[i]][x - 1] + a[i]);
    • 但由于需要求最大 leftpatience ，要保证 j 从 1 到 m 都被遍历过，才能找到最小的 j，否则可能当 i = k 时 b[i] 已经大于本可以最小的 j

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 101				//题目规定最大为100，从1号单元开始用则需要101个单元
using namespace std;

int f[MAX][MAX];			//优化解法，用二维数组，当前层的数据覆盖上一层的数据
int a[MAX];
int b[MAX];

int main() {
	int n, k;			//n还需的经验值，k怪的种数，
	int m, s;			//m保留的忍耐度，s最多的杀怪数
	int flag = 1;			//flag=1表示还没找到可升级的位置
	int leftpatience = -1;	//表示剩余的忍耐度

	while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
		leftpatience = -1;	//重置leftpatience
		flag = 1;			//重置flag
		for (int i = 1; i <= k; i++)
			cin >> a[i] >> b[i];
		//=========================================================================================================
		//优化解法：二维数组，存放所有可能的解
		memset(f, 0, sizeof(f));				//由于二维数组需要循环利用，故【务必】在处理下一组数据前把数组复位，否则在执行max函数时会受影响
		for (int i = 1; i <= k; i++)			//第i个怪，共k个怪
			for (int j = 1; j <= m; j++)		//当前总忍耐度为j，最大忍耐度为m
				for (int x = 1; x <= s; x++)	//当前最多杀怪数为x
				{
					if (j >= b[i])
						f[j][x] = max(f[j][x], f[j - b[i]][x - 1] + a[i]);
					if (i == k && flag && f[j][x] >= n)	//第一次达到升级经验
					{
						leftpatience = m - j;
						flag = 0;
					}
				}
		//=========================================================================================================

		cout << leftpatience << endl << endl;	//升级时剩余的忍耐度
	}
	return 0;
}

还踩了一个OJ平台的坑

杭电OJ平台多个测试数据多次输入应采取如下形式：

while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
    //。。。。。。。
}

而不是 ↓

while(1) {
    cin << n << m << k << s;
}

源源源最源的源代码

/*
* 二维完全背包问题
*
FATE
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 29355    Accepted Submission(s): 13558

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

*/

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 101				//题目规定最大为100，从1号单元开始用则需要101个单元
using namespace std;

//int f[MAX][MAX][MAX];		//一般解法，用三维数组保存所有数据
int f[MAX][MAX];			//优化解法，用二维数组，当前层的数据覆盖上一层的数据
int a[MAX];
int b[MAX];

////测试代码，输出三维表格（一般解法）
//void test3D(int k,int m,int s) {
//	for (int j = 1; j <= m; j++)		//总忍耐度为j
//	{
//		for (int x = 1; x <= s; x++)	//最多杀怪数为x
//		{
//			cout << f[k][j][x] << '\t';
//		}
//		cout << endl;
//	}
//
//	for (int j = 1; j <= m; j++)		//总忍耐度为j
//	{
//		for (int x = 1; x <= s; x++)	//最多杀怪数为x
//		{
//			printf("f[%d][%d][%d] = %d\n", k, j, x, f[k][j][x]);
//			//cout << f[k][j][x] << '\t';
//		}
//		cout << endl;
//	}
//}

////测试代码，输出二维表格（优化解法）
//void test2D(int m, int s) {
//	for (int j = 1; j <= m; j++)		//总忍耐度为j
//	{
//		for (int x = 1; x <= s; x++)	//最多杀怪数为x
//			cout << f[j][x] << '\t';
//		cout << endl;
//	}
//
//	for (int j = 1; j <= m; j++)		//总忍耐度为j
//		for (int x = 1; x <= s; x++)	//最多杀怪数为x
//			printf("f[%d][%d] = %d\n", j, x, f[j][x]);
//}

int main() {
	int n, k;			//n还需的经验值，k怪的种数，
	int m, s;			//m保留的忍耐度，s最多的杀怪数
	int flag = 1;			//flag=1表示还没找到可升级的位置
	int leftpatience = -1;	//表示剩余的忍耐度

	while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
		leftpatience = -1;	//重置leftpatience
		flag = 1;			//重置flag
		//cin >> n >> m >> k >> s;		//OJ中不能这样输入
		for (int i = 1; i <= k; i++)
			cin >> a[i] >> b[i];
		////=========================================================================================================
		////一般解法：三维数组，存放所有可能的解
		//for (int i = 1; i <= k; i++)			//第i个怪，共k个怪
		//	for (int j = 1; j <= m; j++)		//当前总忍耐度为j，最大忍耐度为m
		//		for (int x = 1; x <= s; x++)	//当前最多杀怪数为x
		//		{
		//			if (j < b[i])
		//				f[i][j][x] = f[i - 1][j][x];
		//			else
		//				f[i][j][x] = max(f[i - 1][j][x], f[i][j - b[i]][x - 1] + a[i]);
		//			if (i==k && flag && f[i][j][x] >= n)	//第一次达到升级经验
		//			{
		//				//printf("i=%d\tj=%d\tx=%d\tf[i][j][x]=%d\n", i, j, x, f[i][j][x]);
		//				leftpatience = m - j;
		//				flag = 0;
		//			}
		//		}
		////cout << f[k][m][s] << endl;	//最大能获取的经验
		////test3D(k, m, s);
		////=========================================================================================================

		//=========================================================================================================
		//优化解法：二维数组，存放所有可能的解
		memset(f, 0, sizeof(f));				//由于二维数组需要循环利用，故【务必】在处理下一组数据前把数组复位，否则在执行max函数时会受影响
		for (int i = 1; i <= k; i++)			//第i个怪，共k个怪
			for (int j = 1; j <= m; j++)		//当前总忍耐度为j，最大忍耐度为m
				for (int x = 1; x <= s; x++)	//当前最多杀怪数为x
				{
					if (j >= b[i])
						f[j][x] = max(f[j][x], f[j - b[i]][x - 1] + a[i]);
					if (i == k && flag && f[j][x] >= n)	//第一次达到升级经验
					{
						leftpatience = m - j;
						flag = 0;
					}
				}
		//cout << f[m][s] << endl;	//最大能获取的经验
		//test2D(m, s);
		//=========================================================================================================

		cout << leftpatience << endl << endl;	//升级时剩余的忍耐度
	}
	return 0;
}

参考：2159 ACM 杭电 杀怪 二维费用的背包+完全背包问题，优化版找bug的时候就是和这个里面的代码一个一个字在对比

标签：10,OJ,FATE,xhd,int,MAX,杭电,flag,忍耐
From： https://www.cnblogs.com/Eric-lHHI/p/17491460.html

相关文章

  • Delphi 用TDatasetToJSONBridge原生支持DataSet导出Json
    Xalion发现data.DBJson单元，不知什么时候加的，官方帮助中也没有写。procedureTForm18.Button2Click(Sender:TObject);varcV:TDatasetToJSONBridge;jo:Tjsonobject;begincV:=TDatasetToJSONBridge.Create;trycV.Dataset:=mt;jo:=Tjsonobject(cV.Pro......
  • nginx-clojure debug构建简单说明
    实际上参考了官方的构建参数，提供一个debug模式的文件原始配置configurearguments:--prefix=--sbin-path=nginx--conf-path=conf/nginx.conf--error-log-path=logs/error.log--http-log-path=logs/access.log--pid-path=logs/nginx.pid--lock-path=logs/nginx.lock--http-......
  • nginx-clojure 0.6.0 的一些新特性
    昨天制作了0.6.0的docker镜像，并说明了一些问题，以下简单说明下一些新特性新特性所有的handler可以在http以及servercontext使用了，可以方便进行组合使用nginx1.23.x支持jdk19支持，支持协程了官方提供的二进制构建基于1.23.3说明昨天也说明了，官方提供的二进制包缺少一些依赖，......
  • nginx-clojure 源码构建一些问题
    因为nginx-clojure就是一个标准的nginx模块，一些是尝试基于源码进行构建发现一些问题的说明简单说明nginx当前1.25版本的构建是有问题的,1.24版本构建是可以的，1.23版本实际上官方已经提供了但是如果查看nginx官方文档会发现1.23版本的下载官方是似乎移除了，没直接提供了......
  • nginx-clojure-0.6.0 集成nginx 1.25.0 构建的解决方法
    今天也说过关于nginx-clojure-0.6.0集成nginx1.2.50构建是有问题的，以下是解决方法实际问题staticdeclarationof‘ngx_http_close_request’followsnon-staticdeclaration原因nginx-clojure复制了nginx源码中对于nginx的处理函数（ngx_http_clojure_mem.c文件）/*copyfrom......
  • CMU15445 (Fall 2020) 数据库系统 Project#3 - Query Execution 详解
    前言经过前两个实验的铺垫，终于到了执行SQL语句的时候了。这篇博客将会介绍SQL执行计划实验的实现过程，下面进入正题。总体架构一条SQL查询的处理流程如下为：SQL被Parser解析为抽象语法树ASTBinber将AST转换为Bustub可以理解的更高级的ASTTreerewriter将语法......
  • slojP2105. 锻造
    题目背景勇者虽然武力值很高，但在经历了多次战斗后，发现怪物越来越难打，于是开始思考是不是自己平时锻炼没到位，于是苦练一个月后发现……自己连一个史莱姆都打不过了。勇者的精灵路由器告诉勇者其实是他自己的武器不好，并把他指引到了锻造厂。题目描述“欢迎啊，老朋友。”一阵寒......
  • POJ2117 Electricity 题解 tarjan点双连通分量 割点
    题目链接：http://poj.org/problem?id=2117题目大意：给定一个由\(n\)个点\(m\)解题思路：tarjan，判断\(u\)的子节点有几个\(v\)满足\(low[v]\gedfn[u]\)就是答案，但是同时如果\(u\)不是这个dfs树的根节点，个数还要加\(1\)。示例程序1（C++11，POJ不支持）：#include<bits/stdc++.h>......
  • 【基础算法】单链表的OJ练习(5) # 环形链表 # 环形链表II # 对环形链表II的解法给出证
    前言本章的OJ练习相对于OJ练习(4)较为简单。不过，本章的OJ最重要的是要我们证明为何可以这么做。这也是==面试==中常出现的。对于OJ练习(4)：==->==传送门==<-==，分割链表以一种类似于归并的思想解得，回文链表以一种巧妙复用前面OJ题的思想解得。啰嗦一下：对于本章，最重要的是......
  • 【BZOJ 3156】防御准备 题解
    原题令\(S_{i}=\sum_{j=1}^{i}j\),\(f_{i}\)为处理到第\(i\)个位置放置守卫塔的最小花费。观察题意，容易得到在\((1<=j<=i-1)\)时，有\(f_{i}=min\left\{f_{j}+\sum_{k=j+1}^{i-1}(i-k)+a_{i}\right\}\)①\(f_{i}=min\left\{f_{j}+\sum_{k=j+1}^{i-1}(i-k)\ri......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99