一道DP+贪心
```C++
#include<bits/stdc++.h>
using namespace std;
int n;
int s[5005];
int dp[5005];
int dp2[5005];
int maxn=-0x7f7f7f7f;
int cnt=0;
int main(void)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i];
dp[i]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(s[i]<s[j])dp[i]=max(dp[j]+1,dp[i]);
}
}
for(int i=1;i<=n;i++)maxn=max(maxn,dp[i]);
dp2[1]=1;
int ans=0;
for(int i=1;i<=n;i++)
{
if(dp[i]==1)dp2[i]=1;
for(int j=1;j<i;j++)
{
if(s[i]<s[j]&&dp[i]==dp[j]+1)dp2[i]+=dp2[j];
if(s[i]==s[j] && dp[i]==dp[j])dp2[i]-=dp2[j];
}
if(dp[i]==maxn)
{
ans+=dp2[i];
}
}
cout<<maxn<<" "<<ans;
return 0;
}
```
by 凤凰工作室 @ 2023-01-04 16:41:20