基础课模板题

DP

最长上升子序列

AcWing 3698. 搬箱子

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1010;
int f[N];
int a[N]; 
int n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int res = 0;
    // 动态规划
    for(int i = 1; i <= n; i++){            // f[i]表示以i结尾的上升子序列的最大长度
        f[i] = 1;
        for(int j = 1; j < i; j++){        // 遍历j 按照倒数第二个为j划分集合  [... ji]   以i结尾
            if(a[j] < a[i])
                f[i] = max(f[i],f[j]+1);   // f[i] = max(f[j] + 1);
        }
        res = max(res,f[i]);
    }
    cout << res << endl;
    return 0;
}