做题记录整理dp3 P1108. 低价购买（2022/9/20）

P1108. 低价购买

第一问很明显是一个最长下降子序列

第二问就是一个求方案数，有点难想的就是去重

感觉这题难度标的有点偏高

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i =a;i<=b;i++)
using namespace std;
int a[100005],n,dp[1000005],cnt[1000005],len;
int ans=1,ans2=0;
int main()
{
   cin>>n;   
    for1(i,1,n) cnt[i]=1;
   for1(i,1,n) scanf("%d",&a[i]);
   for1(i,1,n) dp[i]=1;
    for1(i,2,n)
    {
    	for1(j,1,i-1)
    	{
    	    if(a[i]<a[j])
    	    {
    	    	if(dp[i]<dp[j]+1)
                 dp[i]=dp[j]+1,cnt[i]=cnt[j];
                else if(dp[i]==dp[j]+1)
                 cnt[i]+=cnt[j];
            }
            if(a[j]==a[i]) dp[j]=dp[j]=0;//去重
		}
		if(ans<dp[i])
		{
			ans=dp[i];
		}
		 
    }
    cout<<ans;
     for1(i,1,n)
	     if(dp[i]==ans)
		     ans2+=cnt[i];
    cout<<' '<<ans2<<endl;
    return 0;
}