https://blog.csdn.net/csyifanZhang/article/details/106044042

完整题解与解析↑

#define ll long long 
#define inf 0x3ffffff
#define MAX 5005
#define vec vector<ll>

int main() {
	ll N, a[MAX], dp[MAX], c[MAX];
	while (cin >> N) {
		memset(dp, 0, sizeof(dp));
		memset(c, 0, sizeof(c));
		ll maxx = 0, cnt = 0;
		for (int i = 1; i <= N; i++)cin >> a[i];
		for (int i = 1; i <= N; i++) {
			dp[i] = 1;
			for (int j = i - 1; j >= 1; j--) {
				if (a[i]<a[j] && dp[j] + 1 > dp[i])
					dp[i] = dp[j] + 1;
			}
			if (dp[i] == 1)c[i] = 1;//不能组成序列，只有一种组合数
				//注意这个方向是从1-i，而不能从i-1
			for (int j = 1; j < i; j++) {
				if (a[i] < a[j] && dp[j] + 1 == dp[i])
					c[i] += c[j];//i的组合数和j有关
				else if (dp[i] == dp[j] && a[i] == a[j])
					c[i] = 0;//去重，避免完全相同的方案
			}

			if (dp[i] > maxx)maxx = dp[i];
		}
		for (int i = 1; i <= N; i++)
			if (dp[i] == maxx)cnt += c[i];
		cout << ma...