P1108 低价购买

这题其实就是一道最长下降子序列，只是多了一个求方案数
很容易想出方法，设g[i]表示以第i个数结尾的最长下降子序列的方案数
那么每次求完f[i]
便利j=1~i-1
1.f[i]=f[j] 且 a[i]=a[j]
g[j]=0
因为方案数相同且结尾相同，那么前面的方案肯定一样，所以把g[j]置0
2.f[i]=f[j] 且 a[i]<a[j]
g[i]+=g[j]
正好接上，那么方案数也叠加
接下来上代码

#include<bits/stdc++.h>
using namespace std;
int n,a[50005],f[50005],g[50005];
int ans,sum;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++)
			if(a[j]>a[i])
				f[i]=max(f[i],f[j]+1);
		for(int j=1;j<i;j++)
			if(f[i]==f[j] && a[i]==a[j])g[j]=0;
			else if(f[i]==f[j]+1 && a[i]<a[j])g[i]+=g[j];
		if(g[i]==0)g[i]++;
	}
	ans=0;for(int i=1;i<=n;i++)ans=max(ans,f[i]);
	for(int i=1;i<=n;i++)if(f[i]==ans)sum+=g[i];
	printf("%d %d\n",ans,sum);
	return 0;
}