50 pts,心态爆炸
思路如下:
第一问很简单吧,用下面的转移方程求最长下降子序列即可: dp[i]=max{dp[j]}+1 其中 dp[j] 要满足 a[j]≥a[i]。
第二问可以另定义一个数组 sum[i] 代表子序列以 a[i] 结尾长度为 dp[i] 的方案数,所以当 a[i]<a[j] 且 dp[i]=dp[j]+1 的时候: sum[i]=sum[i]+sum[j]
(上面直接粘贴我写的题解)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[5001];
int dp[5001];
double sum[5001];
signed main () {
long long n;
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
int LdS = 0;
for (int i = 1; i <= n; i++) {
int Max = 0;
for (int j = 1; j < i; j++)
if (a[j] >= a[i])
Max = max(Max, dp[j]);
dp[i] = Max + 1;
LdS = max(LdS, dp[i]);
}
printf("%lld ", LdS);
int MAX = LdS;
for (int i = 1; i <= n; i++)
if (dp[i] <= 1)
sum[i] = 1;
else
MAX = max(MAX, dp[i]);
dp[n + 1] = MAX + 1;
for (int i = 2; i <= n + 1; i++)
for (int j = 1; j < i; j++) {
if (a[i] < a[j] && dp[i] == dp[j] + 1)
sum[i] += sum[j];
if (a[i] == a[j] && dp[i] == dp[j])
sum[i] -= sum[j];
}
printf("%.0f", sum[n + 1]);
return 0;
}
禁止无意义回复