题解【POJ1952】 BUY LOW, BUY LOWER

题目意思:

给你一个长度为\(n\)(\(1<=n<=5000\))的序列,并求出最长下降子序列的长度及个数,

并且,如果两个序列中元素的权值完全相同,那么即使它们的位置不一样,也只算一种情况.

解析

长度应该都能轻松求出来吧.

然而,情况数却有点难求啊..

其实主要是去重(要不然用计数\(DP\)也能过)...

但仔细想想,

首先,我们设\(f[i]\)为以\(i\)结尾的最长下降子序列的长度,

\(s[i]\)为以\(i\)结尾的最长上升子序列的个数.

那么对于两个权值相同的元素\(i\),\(j\),且\(i<j\),\(f[i]=f[j]\)(若不等于则不可能造成影响),

那么,以\(i\)结尾的序列,都能用\(j\)替换\(i\),

即\(s[i]\)的情况都会计算到\(s[j]\)中,

所以,在计算\(j\)的时候,将所有\(a[i](\)即权值\()=a[j]\),且\(f[i]=f[j]\)的\(s[i]\)都减掉就行了,

最后,上代码吧:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

int n,a[100001],ans,ret;

int s[100001],f[100001];

int main(){

	n=read();

	s[0]=1;

	for(int i=n;i;i--) a[i]=read();//倒过来也就变成了最长上升子序列,仅仅是个人习惯

	for(int i=1;i<=n;i++){

		int len=0;

		for(int j=1;j<i;j++){

			if(a[i]>a[j]) len=max(len,f[j]);

		}

		f[i]=len+1;

		for(int j=0;j<i;j++){

			if(f[j]==len&&a[j]<a[i]) s[i]+=s[j];

		}

		for(int j=0;j<i;j++) if(a[i]==a[j]&&f[j]==f[i]) s[i]-=s[j];//去重

	}

	for(int i=1;i<=n;i++) ans=max(ans,f[i]);//寻找最长子序列

	for(int i=1;i<=n;i++) if(f[i]==ans) ret+=s[i];//统计答案

	printf("%d %d\n",ans,ret);

	return 0;

}

巴特西

题解【POJ1952】 BUY LOW, BUY LOWER

题目意思:

解析

最新文章

热门文章

巴特西

题解 【POJ1952】 BUY LOW, BUY LOWER

题目意思:

解析

最新文章

热门文章

题解【POJ1952】 BUY LOW, BUY LOWER