记录一种常见的求方案数的思路——基于dp数组的dp。
#include <bits/stdc++.h>
#define MAXN 5001
using namespace std;
int n;
int ansa,ansb;
int a[MAXN];
int dpa[MAXN];
int dpb[MAXN];
int main() {
ios::sync_with_stdio(false);
cin >> n;
for ( int i = 1; i <= n; ++i )
cin >> a[i];
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j < i; ++j )
if ( a[i] < a[j] )
dpa[i] = max(dpa[i], dpa[j] + 1);
ansa = max(ansa, dpa[i]);
}
ansa += 1;
for ( int i = 1; i <= n; ++i ) {
if ( dpa[i] == 0 )
dpb[i] = 1;
for ( int j = 1; j < i; ++j ) {
if ( dpa[i] == dpa[j] + 1 && a[i] < a[j] )
dpb[i] += dpb[j];
if ( dpa[i] == dpa[j] && a[i] == a[j] )
dpb[i] = 0;
}
if ( dpa[i] == ansa - 1 )
ansb += dpb[i];
}
cout << ansa << ' ' << ansb << endl;
return 0;
}