POJ1952 Solution

题目链接

题解

附加统计方案数与去重的类LIS问题。

状态：\(dp_i\)表示\([a_1,a_i]\)的最长下降子序列长度，另设\(sum_i\)表示\([a_1,a_i]\)最长下降子序列出现次数。

初始值：\(dp_i=1,sum_i=1\quad(1\le i\le n)\)

转移：

\[sum_i=sum_j,dp_i=dp_j+1\quad (a_i<a_j,dp_i<dp_j+1)\\ sum_i=sum_i+sum_j(a_i<a_j,dp_i=dp_j+1)\\ (1\le i\le n,i-1\ge j\ge 1) \]

对于去重，将\(j\)倒序循环，如遇\(a_j=a_i\)则下面循环中的前缀序列已经被\(a_j\)统计过了，应跳出循环。但因为长度为\(1\)的子序列是在初始值中预先处理的，若最大长度为\(1\)仍会被多次统计，所以如果\(a_j=a_i\)且\(dp_i=1\)则\(sum_i=0\)。

目标状态：\(ans1=min(dp_i)\quad(1\le i\le n),\quad ans2=\sum\limits_{i=1}^n sum_i\quad(dp_i=ans1)\)

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5010;
int a[N],dp[N],sum[N];
int main()
{
	int n,ans1=0,ans2=0;
	scanf("%d",&n); 
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		dp[i]=1,sum[i]=1;
		for(int j=i-1;j>=1;j--)
		{
			if(a[i]<a[j])
			{
				if(dp[i]==dp[j]+1) sum[i]+=sum[j];
				if(dp[i]<dp[j]+1) sum[i]=sum[j],dp[i]=dp[j]+1;
			}
			if(a[i]==a[j]) 
			{
				if(dp[i]==1) sum[i]=0;
				break; 
			}
		}
	}
	for(int i=1;i<=n;i++) ans1=max(ans1,dp[i]);
	for(int i=1;i<=n;i++)
		if(dp[i]==ans1) ans2+=sum[i];
	printf("%d %d",ans1,ans2);
	return 0;
}