题面描述

给定一组书籍的规格，每本书都有长度和宽度两个整数参数，表示为 $(l, w)$。如果书籍 $A$ 的长度和宽度都严格大于书籍 $B$ 的长度和宽度，则允许将 $B$ 叠放在 $A$ 上面。要求在叠放书籍时，书籍不能旋转（即长度和宽度的方向必须保持不变）。请计算在给定的书籍规格中，最多能够叠放多少本书籍。

思路

1. 排序：

   • 首先将所有书籍按照长度从大到小排序。
   • 如果长度相同，则按照宽度从大到小排序。
   • 这种排序方式确保在后续的DP过程中，当前书籍的长度不会小于之前的书籍，简化了叠放条件的判断。

2. 动态规划：

   • 定义一个数组 dp，其中 dp[i] 表示以第 i 本书作为最上层书籍时，能够叠放的最大书籍数量。
   • 初始化 dp 数组，所有元素初始为 1，因为每本书至少可以单独成为一个堆叠。
   • 对于每本书 i，遍历之前的所有书籍 j（j < i），如果书籍 i 的长度和宽度都严格小于书籍 j，则可以将书籍 i 叠放在书籍 j 上，此时更新 dp[i] = max(dp[i], dp[j] + 1)。

3. 结果：

   • 最终，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