3698. 搬箱子 南京理工大学考研复试上机真题 动态规划线性增长问题
华华要给厂里进一批新箱子共 n 个，编号为 1 到 n，用一个正整数 ai 来表示编号为 i 的箱子的高度。
现在华华要按照编号从小到大的顺序选出 m个箱子运到厂房，要确保编号大的箱子比编号小的箱子高。
也就是对于任意的 i<j 有 ai<a那么 m最大可以是多少呢？
输入格式
第一行是正整数 n，表示 n 个箱子。
第二行 a1,a2…an分别表示编号为 i的箱子的高度。
输出格式
输出华华最多可以搬运的箱子个数。
数据范围
1≤n≤500
1≤ai≤100000
输入样例：
7
1 7 3 5 9 4 8
输出样例：
4#include<bits/stdc++.h>
using namespace std;int n;
int a[600];
int dp[600];
int m =0;
int main()
{cin>>n;for(int i =1; i<=n;i++){cin>>a[i];}/*1.m =12.选 dp[i]=max(m,dp[i-j]+1);*/a[0]=1111111;dp[1]=1;for(int i =2; i<=n;i++){int res=1;for(int j =i-1; j>=1;j--){if(a[i]>a[j]&&res<dp[j]+1){res=dp[j]+1;}}m=max(m,res);dp[i]=res;}for(int i =1; i<=n;i++){// cout<<dp[i]<<" ";}cout<<m<<"\n";return 0;
}