JZTXT

杭电OJ-2159-FATE踩坑记录

发布时间 2023-06-19 16:28:23作者: Eric_Lau

杭电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的时候就是和这个里面的代码一个一个字在对比?