普通dp

最大不连续递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
int num[maxn];
int dp[maxn];
inline int solve(int n){
    for(int i = 0;i < n;i++) dp[i] = 1;
    for(int i = 0;i < n;i++)
        for(int j = 0;j < i;j++){
            if(num[i] > num[j]) dp[i] = max(dp[i], m[j] + 1);
        }
    int ans = 0;
    for(int i = 0;i < n;i++) ans = max(ans, dp[i]);
    return ans;
}