Usaco Training Section 4.3 Buy Low, Buy Lower

又遇到了多年不见的高精度!!!

题目很好懂,求最长下降子序列的长度及个数(相同的算一个)

一开始很激动,样例都没看,以为只求最长下降子序列的长度。直接把序列倒过来,跑一个lis,O(nlogn)。后来发现还要求个数,崩溃*1。很快发现其实还好,只不过好像个数只能O(n^2)来求。还有个头疼的问题,相同的只能算一个,于是我开始乱搞,用map+set,写了好长,崩溃*2,一交,NO!!!还要高精度!!!崩溃*3。加了个高精度(因为我的写法比较奇怪,涉及了高精加和高精减),一交,TLE!崩溃*4。于是想开n个树状数组,但发现貌似会MLE,因为USACO Training的内存好像只给了16M。崩溃*5。于是我想了好久。突然发现,对于f[i]和a[i]都相等的数可以直接忽略(a[i]表示第i个数的值,f[i]表示到a[i]为止的LIS长度)。这下就好做了。于是……过了。

法一:n^2lis+n^2dp

#include<bits/stdc++.h>
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
using namespace std;

inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

int a[5005],f[5005];
string ans[5005];
int c[305],b[305];

inline string add(string s1,string s2){
    int n=s1.length(),m=s2.length();
    if(n<m) swap(n,m),swap(s1,s2);
    for(int i=n;i;--i) c[i]=s1[n-i]-48;
    for(int i=m;i;--i) b[i]=s2[m-i]-48;
    for(int i=m+1;i<=n;++i) b[i]=0;
    c[n+1]=0;
    for(int i=1;i<=n;++i) c[i+1]+=(c[i]+b[i])/10,c[i]=(c[i]+b[i])%10;
    if(c[n+1]>0) ++n;
    string s="";
    for(int i=n;i;--i) s+=c[i]+48;
    return s;
}

int main()
{
    freopen("buylow.in","r",stdin);
    freopen("buylow.out","w",stdout);
    int n=read();
    for(int i=n;i;--i) a[i]=read(),ans[i]="0";
    a[++n]=inf;
    ans[0]="1";
    for(int i=1;i<=n;++i){
        for(int j=0;j<i;++j)
            if(a[i]>a[j]&&f[j]+1>f[i]) f[i]=f[j]+1;
        for(int j=i-1;j>=0;--j){
            if(f[j]==f[i]&&a[j]==a[i]) break;
            if(f[j]+1==f[i]&&a[j]<a[i]) ans[i]=add(ans[i],ans[j]);
        }
    }
    cout<<f[n]-1<<' '<<ans[n]<<'\n';
}

法二:nlogn lis+n^2dp

#include<bits/stdc++.h>
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
using namespace std;

inline int read(){
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

int a[5005],f[5005],dp[5005];
string ans[5005];
int c[305],b[305];

inline string add(string s1,string s2){
    int n=s1.length(),m=s2.length();
    if(n<m) swap(n,m),swap(s1,s2);
    for(int i=n;i;--i) c[i]=s1[n-i]-48;
    for(int i=m;i;--i) b[i]=s2[m-i]-48;
    for(int i=m+1;i<=n;++i) b[i]=0;
    c[n+1]=0;
    for(int i=1;i<=m;++i) c[i+1]+=(c[i]+b[i])/10,c[i]=(c[i]+b[i])%10;
    if(c[n+1]>0) ++n;
    string s="";
    for(int i=n;i;--i) s+=c[i]+48;
    return s;
}

int main()
{
    freopen("buylow.in","r",stdin);
    freopen("buylow.out","w",stdout);
    int n=read(),m=0;
    for(int i=n;i;--i) a[i]=read(),ans[i]="0";
    for(int i=1;i<=n;++i){
        int x=lower_bound(dp+1,dp+m+1,a[i])-dp;
        dp[x]=a[i];
        f[i]=x;
        x>m?m=x:x=x;
    }
    ans[0]="1";
    for(int i=1;i<=n;++i){
        for(int j=i-1;j>=0;--j){
            if(f[j]==f[i]&&a[j]==a[i]) break;
            if(f[j]+1==f[i]&&a[j]<a[i]) ans[i]=add(ans[i],ans[j]);
        }
        if(f[i]==m) ans[n+1]=add(ans[n+1],ans[i]);
    }
    cout<<m<<' '<<ans[n+1]<<'\n';
}

发现usaco training的section4里的题目难度明显有了提升。这题也挺有质量的。以前从没见过求LIS的个数。而且这题要一次做对也不简单,高精度……真的容易被忽略。

原文链接:加载失败,请重新获取