把n个数离散化,之后每次从后往前计算方案数,遇到相同的数就跳过
最后计算答案也一样
C++ 代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
int n;
int a[5001],t[5001];
map <int,int> m;
int idx=0;
bool vis[5001];
int f[5001];
long long cnt[5001];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),t[i]=a[i];
sort(t+1,t+n+1);
for (int i=1;i<=n;i++)
{
if (!m.count(t[i])) m[t[i]]=++idx;
}
for (int i=1;i<=n;i++) a[i]=m[a[i]];
f[1]=1; cnt[1]=1;
for (int i=2;i<=n;i++)
{
f[i]=1;
for (int j=i-1;j>=1;j--)
{
if (a[j]>a[i]) f[i]=max(f[i],f[j]+1);
}
if (f[i]==1) cnt[i]=1;
else
{
for (int j=1;j<=idx;j++) vis[j]=false;
for (int j=i-1;j>=1;j--)
{
if (a[j]>a[i]&&f[j]+1==f[i]&&!vis[a[j]])
{
vis[a[j]]=true;
cnt[i]+=cnt[j];
}
}
}
// printf("!%d %d %lld\n",i,f[i],cnt[i]);
}
int ans=0;
long long c=0;
for (int i=1;i<=n;i++) ans=max(ans,f[i]);
for (int i=1;i<=idx;i++) vis[i]=false;
for (int i=n;i>=1;i--)
{
if (ans==f[i]&&!vis[a[i]]) c+=cnt[i],vis[a[i]]=true;
}
printf("%d %lld",ans,c);
return 0;
}