#P3212. 书籍叠放(200分)
-
1000ms
Tried: 91
Accepted: 34
Difficulty: 5
所属公司 :
华为od
书籍叠放(200分)
题面描述
给定一组书籍的规格,每本书都有长度和宽度两个整数参数,表示为 (l,w)。如果书籍 A 的长度和宽度都严格大于书籍 B 的长度和宽度,则允许将 B 叠放在 A 上面。要求在叠放书籍时,书籍不能旋转(即长度和宽度的方向必须保持不变)。请计算在给定的书籍规格中,最多能够叠放多少本书籍。
思路
-
排序:
- 首先将所有书籍按照长度从大到小排序。
- 如果长度相同,则按照宽度从大到小排序。
- 这种排序方式确保在后续的DP过程中,当前书籍的长度不会小于之前的书籍,简化了叠放条件的判断。
-
动态规划:
- 定义一个数组
dp,其中dp[i]表示以第i本书作为最上层书籍时,能够叠放的最大书籍数量。 - 初始化
dp数组,所有元素初始为1,因为每本书至少可以单独成为一个堆叠。 - 对于每本书
i,遍历之前的所有书籍j(j < i),如果书籍i的长度和宽度都严格小于书籍j,则可以将书籍i叠放在书籍j上,此时更新dp[i] = max(dp[i], dp[j] + 1)。
- 定义一个数组
-
结果:
- 最终,
dp数组中的最大值即为最多可以叠放的书籍数量。
- 最终,
cpp
#include <bits/stdc++.h>
using namespace std;
// 函数:解析输入字符串,提取书籍规格
vector<vector<int>> parseInput(const string& input) {
vector<vector<int>> books;
vector<int> current;
int num = 0;
bool num_started = false;
for(char ch : input){
if(ch == '['){
current.clear();
}
else if(ch == ']'){
if(num_started){
current.push_back(num);
num = 0;
num_started = false;
}
if(!current.empty()){
books.push_back(current);
}
}
else if(isdigit(ch)){
num = num * 10 + (ch - '0');
num_started = true;
}
else if(ch == ','){
if(num_started){
current.push_back(num);
num = 0;
num_started = false;
}
}
// 忽略其他字符
}
return books;
}
// 计算最多能叠放的书籍数量(动态规划方法)
int maxStackBooksDP(vector<vector<int>>& books) {
int n = books.size();
if(n == 0) return 0;
// 第一步:排序
sort(books.begin(), books.end(), [&](const vector<int>& a, const vector<int>& b) -> bool {
if(a[0] != b[0])
return a[0] > b[0]; // 按长度从大到小
return a[1] > b[1]; // 长度相同按宽度从大到小
});
// 第二步:初始化DP数组
vector<int> dp(n, 1); // 每本书至少可以单独堆叠
// 第三步:动态规划
for(int i = 1; i < n; ++i){
for(int j = 0; j < i; ++j){
// 如果第i本书可以叠放在第j本书上
if(books[i][0] < books[j][0] && books[i][1] < books[j][1]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
// 第四步:找到DP数组中的最大值
return *max_element(dp.begin(), dp.end());
}
int main(){
// 读取整个输入作为字符串
string input;
getline(cin, input);
// 解析输入字符串,获取书籍列表
vector<vector<int>> books = parseInput(input);
// 计算结果
int result = maxStackBooksDP(books);
// 输出结果
cout << result;
return 0;
}
python
import re
def parse_input(input_str):
"""
解析输入字符串,提取书籍规格。
输入格式:[[20,16],[15,11],[10,10],[9,10]]
输出格式:[[20,16], [15,11], [10,10], [9,10]]
"""
# 使用正则表达式提取所有数字
numbers = list(map(int, re.findall(r'\d+', input_str)))
# 将数字按每两个一组分割
books = [numbers[i:i+2] for i in range(0, len(numbers), 2)]
return books
def max_stack_books_dp(books):
"""
使用动态规划方法计算最多能叠放的书籍数量。
"""
n = len(books)
if n == 0:
return 0
# 第一步:排序
# 按照长度从大到小排序,如果长度相同,则按照宽度从大到小排序
books.sort(key=lambda x: (-x[0], -x[1]))
# 第二步:初始化DP数组
dp = [1] * n # 每本书至少可以单独堆叠
# 第三步:动态规划
for i in range(1, n):
for j in range(i):
# 如果第i本书可以叠放在第j本书上
if books[i][0] < books[j][0] and books[i][1] < books[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
# 第四步:找到DP数组中的最大值
return max(dp)
if __name__ == "__main__":
import sys
# 读取整个输入作为字符串
input_str = sys.stdin.read().strip()
# 解析输入字符串,获取书籍列表
books = parse_input(input_str)
# 计算结果
result = max_stack_books_dp(books)
# 输出结果
print(result)
java
import java.util.*;
import java.util.regex.*;
public class Main {
// 函数:解析输入字符串,提取书籍规格
public static List<int[]> parseInput(String input) {
List<int[]> books = new ArrayList<>();
Matcher m = Pattern.compile("\\d+").matcher(input);
List<Integer> numbers = new ArrayList<>();
while(m.find()){
numbers.add(Integer.parseInt(m.group()));
}
for(int i=0; i<numbers.size(); i+=2){
if(i+1 < numbers.size()){
books.add(new int[]{numbers.get(i), numbers.get(i+1)});
}
}
return books;
}
// 计算最多能叠放的书籍数量(动态规划方法)
public static int maxStackBooksDP(List<int[]> books) {
int n = books.size();
if(n == 0) return 0;
// 转换为二维数组便于排序
int[][] bookArray = new int[n][2];
for(int i=0; i<n; i++){
bookArray[i][0] = books.get(i)[0];
bookArray[i][1] = books.get(i)[1];
}
// 第一步:排序
Arrays.sort(bookArray, new Comparator<int[]>() {
public int compare(int[] a, int[] b){
if(a[0] != b[0]){
return b[0] - a[0]; // 按长度从大到小
}
return b[1] - a[1]; // 长度相同按宽度从大到小
}
});
// 第二步:初始化DP数组
int[] dp = new int[n];
Arrays.fill(dp, 1); // 每本书至少可以单独堆叠
// 第三步:动态规划
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
// 如果第i本书可以叠放在第j本书上
if(bookArray[i][0] < bookArray[j][0] && bookArray[i][1] < bookArray[j][1]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// 第四步:找到DP数组中的最大值
int max = 0;
for(int val : dp){
if(val > max){
max = val;
}
}
return max;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
// 读取整个输入作为字符串
String input = sc.nextLine();
// 解析输入字符串,获取书籍列表
List<int[]> books = parseInput(input);
// 计算结果
int result = maxStackBooksDP(books);
// 输出结果
System.out.println(result);
}
}
题目内容
书籍的长、宽都是整数对应 (l,w)。
如果书 A 的长宽度都比 B 长宽大时,则允许将 B 排列放在 A 上面。
现在有一组规格的书籍,书籍叠放时要求书籍不能做旋转,请计算最多能有多少个规格书籍能叠放在一起。
输入描述
输入:books=[[20,16],[15,11],[10,10],[9,10]]
说明:总共 4 本书籍,第一本长度为 20 宽度为 16 ;
第二本书长度为 15 宽度为 11 ,
依次类推,最后一本书长度为 9 宽度为 10 。
输出描述
输出:3
说明: 最多 3 个规格的书籍可以叠放到一起, 从下到上依次为: [20,16],[15,11],[10,10]。
样例1
输入
[[20,16],[15,11],[10,10],[9,10]]
输出
3