[USACO4.3]逢低吸纳Buy Low, Buy Lower题解

题解"/>

[USACO4.3]逢低吸纳Buy Low, Buy Lower题解

[USACO4.3]逢低吸纳Buy Low, Buy Lower

题目链接
洛谷P2687

思路
这一题第一问还简单，就是要我们求最长下降子序列。可以用n^2算法。

第二问问本质不同的最长下降子序列的种数，先不考虑本质不同，可以设a[i]为第i天的股价，f[i]为以i结尾有多长，s[i]为有多少种序列，则s[i]等于长度为f[i]-1的序列种数之和。

考虑到本质相同，其实就是重复的数字只算一次，如果a[i]==a[j]&&f[i]==f[j],(1<=j<i),那么j完全没必要保留，可以直接令s[j]=0，以后就不会被记进来了。

再提一个坑点，种数会爆long long，所以要用高精度。
code：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[5010],f[5010];
struct int128
{int f[100],tot;void clear()//清零{for(int i=0;i<=99;i++)f[i]=0;tot=0;}void out()//输出{for(int i=tot;i>=1;i--)printf("%d",f[i]);printf("\n");}int128 operator + (const int128 &a)const//重载高精加{int128 c;c.clear();c.tot=a.tot>tot?a.tot:tot;int x=0;for(int i=1;i<=c.tot;i++){c.f[i]=a.f[i]+f[i]+x;x=c.f[i]/10;c.f[i]%=10;}if(x)c.f[++c.tot]=1;return c;}
};
int128 s[5010],num;
int main()
{int n,ans=0;scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%d",&a[i]);for(int i=1; i<=n; i++){int t=0;for(int j=i-1; j>=1; j--)//最长下降子序列if(a[i]<a[j]&&f[j]>t)t=f[j];f[i]=t+1;if(f[i]==1)s[i].tot=s[i].f[1]=1;for(int j=i-1;j>=1;j--){if(a[i]<a[j]&&f[j]==t)//统计s[i]s[i]=s[i]+s[j];else if(a[i]==a[j]&&f[i]==f[j])//如果a[i]==a[j]&&f[i]==f[j],将s[j]清零s[j].clear();}ans=ans>t+1?ans:t+1;}for(int i=1; i<=n; i++)if(f[i]==ans)num=num+s[i];//统计答案printf("%d ",ans);num.out();return 0;
}