题解：积木叠放问题（Tiling Up Blocks）

题目分析

本题要求将给定的积木块叠成最高的塔，每个积木块有两个参数(l, m)，且一个积木块(l, m)只能叠放在另一个积木块(l', m')上，当且仅当l ≥ l'且m ≥ m'。目标是计算出最高的叠放高度，并统计有多少种不同的叠放方式可以达到这个高度。

方法思路

1. 动态规划：利用二维数组dp[i][j]表示参数为(i, j)的积木块能够达到的最大高度。
2. 预处理：使用二维数组w[i][j]统计每种参数的积木块出现的次数。
3. 状态转移：对于每个参数(i, j)，其最大高度为dp[i-1][j]和dp[i][j-1]中的较大值加上当前参数的积木块数量。
4. 结果计算：最终结果存储在dp[100][100]中，因为题目中li和mi的范围是1到100。

解决代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 105
int n, w[N][N], dp[N][N];
int main ()
{
    int a, b;
    while(scanf("%d",&n),n)
    {
        memset(dp,0,sizeof(dp));
        memset(w,0,sizeof(w));
        for(int i = 1; i <= n; i++) {scanf("%d %d",&a,&b); w[a][b]++;}
        for(int i = 1; i <= 100; i++)
        {
            for(int j = 1; j <= 100; j++)
            {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])+w[i][j];
            }
        }
        printf("%d\n",dp[100][100]);
    }
    printf("*\n");
    return 0;
}

代码解释

1. 输入处理：循环读取每组测试数据，直到输入的n为0。
2. 初始化：使用memset将dp和w数组初始化为0。
3. 统计积木块：读取每个积木块的参数(a, b)，并在w[a][b]中计数。
4. 动态规划：双重循环遍历所有可能的参数值(i, j)，计算每个位置的最大高度。
5. 输出结果：每组测试数据处理完毕后，输出dp[100][100]的值。

复杂度分析

• 时间复杂度：$O(100 \times 100 \times T)$，其中$T$是测试数据的组数。
• 空间复杂度：$O(100 \times 100)$，主要用于存储dp和w数组。

该方法通过动态规划高效地解决了积木叠放问题，确保了在给定约束条件下的最优解。