最长上升子序列长度及其个数

 int a[MAXN];

    
 int dp[MAXN];
    
  
    
 int lis = 0;
    
 for (int i = 0; i < n; i++) {
    
     dp[i] = 1;
    
     for (int j = 0; j < i; j++) {
    
     if (a[j] < a[i])
    
         dp[i] = max(dp[i], dp[j] + 1);
    
     }
    
     lis = max(lis, dp[i]);
    
 }

 int a[MAXN];

    
 int dp[MAXN];
    
  
    
 int lis = 0;
    
 for (int i = 0; i < n; i++) {
    
     *lower_bound(dp, dp + n, a[i]) = a[i];
    
 }
    
 lis = lower_bound(dp, dp + n, INF) - dp;

 #include <cstdio>

    
 #include <algorithm>
    
  
    
 using namespace std;
    
  
    
 const int MAXN = 1000;
    
 typedef pair<int, int> P;
    
  
    
 int a[MAXN];
    
 P dp[MAXN];     //dp[i].first表示以a[i]结尾的最长上升子序列长度，dp[i].second表示满足该长度的子序列个数
    
  
    
 int main()
    
 {
    
     //输入序列
    
     int n;
    
     scanf("%d", &n);
    
     for (int i = 0; i < n; i++) {
    
     scanf("%d", &a[i]);
    
     }
    
     
    
     int lis = 0;
    
     for (int i = 0; i < n; i++) {
    
     dp[i].first = 1;
    
     for (int j = 0; j < i; j++) {
    
         if (a[j] < a[i]) {
    
             dp[i].first = max(dp[i].first, dp[j].first + 1);
    
         }
    
     }
    
     
    
     //满足最长上升子序列长度的序列个数为长度为dp[i].first-1且a[j]<a[i]的个数
    
     //即将a[i]填入长度为dp[i].first-1的序列末尾
    
     for (int j = i - 1; j >= 0; j--) {
    
         if (dp[j].first == dp[i].first - 1 && a[j] < a[i]) {
    
             dp[i].second++;
    
         }
    
     }
    
     
    
     lis = max(lis, dp[i].first);
    
     }
    
     
    
     printf("%d\n", lis);
    
     
    
     int ans = 0;
    
     for (int i = 0; i < n; i++) {
    
     if (dp[i].first == lis) {
    
         ans += dp[i].second;
    
     }
    
     }
    
     
    
     printf("%d\n", ans);
    
     
    
     return 0;
    
 }