和LIS反着
本题直接做就行，
注意计算方案数，不是说找到最大的方案，然后再找比他小的就可以了，还要注意去重，所以再建立一个数组c;记录方案数目
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 const int maxn = 5e3 + 10; 5 int n,a[maxn],dp[maxn]; 6 int maxx,c[maxn],ans; 7 signed main(){ 8 //freopen("in","r",stdin); 9 ios::sync_with_stdio(0); 10 cin >> n; 11 for(int i = 1; i <= n; i++) 12 cin >> a[i]; 13 for(int i = 1; i <= n; i++){ 14 dp[i] = 1; 15 for(int j = 1; j < i; j++){ 16 if(a[j] > a[i]){ 17 dp[i] = max(dp[i],dp[j] + 1); 18 } 19 } 20 maxx = max(dp[i],maxx); 21 } 22 for (int i = 1; i <= n; i++) { 23 if (dp[i] == 1) c[i] = 1; 24 for (int j = 1; j < i; j++) { 25 //去重 26 if (dp[i] == dp[j] && a[i] == a[j]) 27 c[i] -= c[j]; 28 if (dp[j] + 1 == dp[i] && a[j] > a[i]) 29 c[i] += c[j]; 30 } 31 } 32 for(int i = 1; i <= n; i++){ 33 if(dp[i] == maxx) 34 ans += c[i]; 35 } 36 cout << maxx << " " << ans << endl; 37 return 0; 38 }