低价购买[DP]

​​传送门​​

dp[i]表示到i的方案数

注意去重

#include<bits/stdc++.h>
#define N 5050
using namespace std;
int f[N],n,a[N],dp[N],ans1=1,ans2;
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=1;
  for(int i=2;i<=n;i++){ 
    for(int j=1;j<i;j++)
      if(a[i]<a[j]) f[i]=max(f[i],f[j]+1);
    ans1 = max(ans1 , f[i]);
  }
  for(int i=1;i<=n;i++){ 
    if(f[i]==1) dp[i] = 1; 
    for(int j=1;j<i;j++){ 
      if(f[j] + 1 == f[i]&& a[i] < a[j]) dp[i] += dp[j];
      else if(f[j] == f[i] && a[i] == a[j]) dp[i] = 0;
    } 
    if(f[i] == ans1) ans2 += dp[i];
  }printf("%d %d",ans1,ans2); return 0;
}