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

· · 题解

定义一个f数组，记录1-i的最长下降子序列

定义一个s数组，记录方案数

代码如下：

#include<bits/stdc++.h>
#define MAXN 5100
using namespace std;
typedef long long ll;
ll n;
ll a[MAXN],s[MAXN],f[MAXN];
int main()
{
    int i,j;
    scanf("%lld",&n);
    for(i=1;i<=n;i++) scanf("%lld",&a[i]);//输入
    s[0]=1;a[0]=LONG_MAX;
    for(i=1;i<=n;i++)
    {
        for(j=i-1;j>=0;j--)//最长下降子序列 
        {
            if(a[j]>a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
        for(j=i-1;j>=0;j--)//记录方案数 
        {
            //如果是这一个方案 
            if(a[j]>a[i] && f[i]==f[j]+1) s[i]=s[i]+s[j];
            //如果有重复，就不找了 
            if(a[i]==a[j] && f[i]==f[j]) break;
        }
    }
    ll t1=0,t2;
    for(i=1;i<=n;i++)//在查找一次 
    {
        if(f[i]>t1)
        {
            t1=f[i];
            t2=s[i];
        }
        else if(f[i]==t1) t2=t2+s[i];
    }
    printf("%lld %lld\n",t1,t2);//输出 
    return 0;
}

这样会错一个点，原因是方案数会炸，所以必须改为高精度

代码如下：

#include<bits/stdc++.h>
#define MAXN 5100
using namespace std;
typedef long long ll;
int n;
int a[MAXN],f[MAXN];
int s[MAXN][210];
void jiafa(int x,int y)
{
    int i;
    s[x][0]=max(s[x][0],s[y][0]);//找最大值 
    for(i=1;i<=s[x][0];i++)//加法 
    {
        s[x][i]=s[x][i]+s[y][i];
    }
    for(i=1;i<=s[x][0];i++)//进位 
    {
        s[x][i+1]+=s[x][i]/10;
        s[x][i]%=10;
    }
    if(s[x][s[x][0]+1]>0) s[x][0]++;//加法只用判断一次 
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    s[0][0]=s[0][1]=1;//高精度数组，s[0]表示长度 
    a[0]=INT_MAX;
    for(i=1;i<=n;i++)
    {
        for(j=i-1;j>=0;j--)
        {
            if(a[j]>a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
        for(j=i-1;j>=0;j--)
        {
            if(a[j]>a[i] && f[i]==f[j]+1) jiafa(i,j);//增加，相当于前面的s[i]+=s[j] 
            if(a[i]==a[j] && f[i]==f[j]) break;
        }
    }
    int maxx=0;
    for(i=1;i<=n;i++) maxx=max(maxx,f[i]);
    for(i=1;i<=n;i++) if(f[i]==maxx) jiafa(MAXN-1,i);
    printf("%d ",maxx);
    for(i=s[MAXN-1][0];i>=1;i--) printf("%d",s[MAXN-1][i]);
    printf("\n");
    return 0;
}