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

「QQ红包」 · 2017-10-09 16:51:32 · 题解

题解by:redbag

求最长下降子序列

因为n不超过5000，所以O(n^2)复杂度可以接受。

那么我们就可以按照平时求最长单调递减子序列的方法，在求的时候加上一个辅助数组c[i]记录从开始到第i个位置，单调递减子序列为dp[i]时的方案数。

然而,所有的加法都要用高精度

/*
ID: ylx14271
PROG: buylow
LANG: C++     
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
int a[5010];//每个数 
int f[5010];//最长不下降子序列 
int c[5010][100];//统计
int lc[5010];
int sum[100];
int d[100],l,ls;
int ans; 
int n;
int i,j,k;
using namespace std;
void add(int x)//高精加 
{
    ls=max(lc[x],ls);
    ls++;
    for (j=1;j<=ls;j++)
    {
        sum[j+1]=sum[j+1]+(sum[j]+c[x][j])/10;
        sum[j]=(sum[j]+c[x][j])%10;
    }
    if (sum[ls]==0) ls--; 
}
void add1(int x,int y)//高精加 c[x]=c[x]+c[y]
{
    lc[x]=max(lc[x],lc[y])+1;
    for (k=1;k<=lc[x];k++)
    {
        c[x][k+1]=c[x][k+1]+(c[x][k]+c[y][k])/10;
        c[x][k]=(c[x][k]+c[y][k])%10;
    }
    if (c[x][lc[x]]==0) lc[x]--; 
}
int main()
{
    freopen("buylow.in","r",stdin);
    freopen("buylow.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i]=0;
        lc[i]=1;//长度 
        c[i][1]=1;
        for (j=i-1;j>=1;j--)
        {
            if (a[j]>a[i])
            {
                if (f[j]>f[i]) 
                {
                    f[i]=f[j];//求最长下降子序列长度 
                    //以下相当于c[i]=c[j];长度一样直接赋上去 
                    memset(c[i],0,sizeof(c[i]));//一定要清0 
                    lc[i]=lc[j]; 
                    for (k=1;k<=lc[i];k++)
                    {
                        c[i][k]=c[j][k];
                    }
                } else if(f[j]==f[i])
                {//长度一样方案数就加上 
                    //以下相当于 c[i]+=c[j]; 
                     add1(i,j);
                } 
            } else
            {
                if (a[i]==a[j])//a[i]与a[j]相等，形成的序列相同，就不管了 
                {//用第i个位置上的数字替换第j个位置上的数字，形成的序列完全相同  
                    if (f[i]==0) 
                    {
                        //以下相当于c[i]=0; 
                        lc[i]=1;
                        c[i][1]=0; 
                    }
                    break;
                }
            }
        }
        f[i]++;
        ans=max(ans,f[i]);
    }
    for (i=1;i<=n;i++)
    {
        if (f[i]==ans)//其实这一句就是if (f[i]==ans) sum+=c[i];要用高精度 
        {
            memset(d,0,sizeof(d));
            l=0;
            add(i); 
        }    
    }  
    printf("%d ",ans);
    int flag=0;
    for (i=ls+1;i>=1;i--)//高精度输出
    {
        if (flag==1) printf("%d",sum[i]); else
        if (sum[i]!=0) flag=1,printf("%d",sum[i]);
    }
    if (flag==0) printf("0");
    printf("\n");
    return 0;
}

当然不带高精度的看着爽点.

当然会wa,但是方法没错.

然而直接复制不带高精度的代码,就说我题解错了的.

那我还是不放了.