搬箱子-南京理工大学

2023 年 08 月 06 日

358 次浏览

252字数

[来自KeChang](https://blog.silvery.me/)

> 华华要给厂里进一批新箱子共 n 个，编号为 1 到 n，用一个正整数 ai 来表示编号为 i 的箱子的高度。
> 
> 现在华华要按照编号从小到大的顺序选出 m 个箱子运到厂房，要确保编号大的箱子比编号小的箱子高。也就是对于任意的 i<j 有 ai<aj，那么 m 最大可以是多少呢？

### 输入格式

第一行是正整数 n ，表示 n 个箱子。

第二行 a1,a2…an 分别表示编号为 i 的箱子的高度。

### 输出格式

输出华华最多可以搬运的箱子个数。

### 数据范围

1≤n≤500 , 1≤ai≤10000

### 输入样例：

```
7
1 7 3 5 9 4 8
```

### 输出样例：

```
4
```

### 题目分析

DP
对下标为 `i` 的箱子， 有公式 `ansi = max(ansj + 1, 1)` 其中 `ansj` 为 `j` 箱子能组成的最大的箱子序列, 且 `j` 箱的高度小于 `i`箱。

### 代码实现

```
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e2 + 10;

int n, arr[N], dp[N], ans;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for (int j = 0; j <= i; ++j) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
                ans = max(dp[i], ans);
            }
        }
    }
    cout << ans;
    return 0;
}
```

最后修改：2023 年 08 月 06 日