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

破忆 · 2019-06-10 20:58:08 · 题解

题目大意

求最长降序列，并求出不同的方案数

解法

第一问

求最长降序列

因为n只有5000，所以O（n²）的DP即可解决

f[i]表示以i为结尾，其中第i个必取最长上降序列的长度

从之前的数中找上一状态即可

for(int j=1;j<i;j++) if(a[i]<a[j]) f[i]=max(f[i],f[j]+1);

第二问

求方案数

与前一问的DP类似

这里num[i]表示以第i个为结尾，长度为f[i]的方案数

从前面找上一状态累计上即可

if(a[i]<a[j]&&f[i]==f[j]+1) num[i]+=num[j];

但题目要求方案各不相同

特判一模一样的情况，并且减去即可

if(a[i]==a[j]&&f[i]==f[j]) num[i]-=num[j];

细节

因为答案可能会很大，需要高精

但此题数据用double也行

代码

#include<bits/stdc++.h>
using namespace std;
int a[5005],n,f[5005],ans=1;
double num[5005];//类型换成double，勉强可以通过
int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
//  freopen("buylow.in","r",stdin);
//  freopen("buylow.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),f[i]=1;
    for(int i=2;i<=n;i++)
    for(int j=1;j<i;j++) if(a[i]<a[j]) f[i]=max(f[i],f[j]+1);//第一问
    for(int i=1;i<=n;i++) if(f[i]>1) ans=max(ans,f[i]);else num[i]=1;//如果是序列开头，方案就是1
    f[n+1]=ans+1;//方便起见，把答案累计在第n+1项上
    for(int i=2;i<=n+1;i++)
    for(int j=1;j<i;j++){
        if(a[i]<a[j]&&f[i]==f[j]+1) num[i]+=num[j];//刚好是上一状态
        if(a[i]==a[j]&&f[i]==f[j]) num[i]-=num[j];//一样的序列
    }
    printf("%lld %.0lf\n",ans,num[n+1]);
    return 0;
}