O(n^2)+bool判重

#include<cstdio>
#include<cstring>
#define max(a,b)(a>b?a:b)
using namespace std;

long n,a[5001],f[5001],tot[5001][100],ans[100],maxn=0;
bool visit[20000];
void input(){
    freopen("buylow.in","r",stdin);
    scanf("%d",&n);
    for(long i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[i]=1;
    }
}
void add(long *a,long *b,long *c){
    long cc[100];
    memset(cc,0,sizeof(cc));
    cc[0]=max(a[0],b[0]);
    for(long i=1;i<=cc[0];i++)
        cc[i]=a[i]+b[i];
    for(long i=1;i<=cc[0];i++){
        cc[i+1]+=cc[i]/10;
        cc[i]%=10;
    }
    if(cc[cc[0]+1]>0) cc[0]++;
    memcpy(c,cc,sizeof(long)*100);
}
void solve(){
    for(long i=1;i<=n;i++){
        for(long j=1;j<=i-1;j++)
            if(a[i]<a[j] && f[i]<f[j]+1) f[i]=f[j]+1;
        maxn=max(maxn,f[i]);
    }
    for(long i=1;i<=n;i++)
        if(f[i]==1){
            memset(tot[i],0,sizeof(tot[i]));
            tot[i][0]=1;
            tot[i][1]=1;
        }
        else{
            memset(tot[i],0,sizeof(tot[i]));
            tot[i][0]=1;
            memset(visit,1,sizeof(visit));
            for(long j=i-1;j>=1;j--)
                if(f[i]==f[j]+1 && a[i]<a[j] && visit[a[j]]){
                    add(tot[i],tot[j],tot[i]);
                    visit[a[j]]=0;
               }
        }
    memset(visit,1,sizeof(visit));
    for(long i=n;i>=1;i--)
        if(f[i]==maxn && visit[a[i]]){
            add(ans,tot[i],ans);
            visit[a[i]]=0;
        }
}
void output(){
    freopen("buylow.out","w",stdout);
    printf("%d ",maxn);
    for(long i=ans[0];i>1;i--) printf("%d",ans[i]);
    printf("%d\n",ans[1]);
}
int main()
{
    input();
    solve();
    output();
    return 0;
}

速度：
Executing...
   Test 1: TEST OK [0.022 secs, 4732 KB]
   Test 2: TEST OK [0.000 secs, 4732 KB]
   Test 3: TEST OK [0.000 secs, 4732 KB]
   Test 4: TEST OK [0.011 secs, 4732 KB]
   Test 5: TEST OK [0.011 secs, 4728 KB]
   Test 6: TEST OK [0.022 secs, 4728 KB]
   Test 7: TEST OK [0.043 secs, 4732 KB]
   Test 8: TEST OK [0.022 secs, 4732 KB]
   Test 9: TEST OK [0.043 secs, 4732 KB]
   Test 10: TEST OK [0.227 secs, 4728 KB]

O(nlongn):

#include<iostream>
using namespace std;
int n,a[5000],f[5000],c[5000],size;
int tot[5000][30],ans[30];
int bsearch(int *ci,int ai){
    int l=1,r=size-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(ai<ci[mid-1]&&ai>=c[mid]) return mid;
        else if(ai<ci[mid]) l=mid+1;
        else r=mid-1;
    }
}
void add(int *ai,int *bi){
    if(bi[0]>ai[0]) ai[0]=bi[0];
    for(int i=1;i<=ai[0];++i) ai[i]+=bi[i];
    for(int i=1;i<=ai[0];++i){
        ai[i+1]+=ai[i]/10000;
        ai[i]%=10000;
    }
    if(ai[ai[0]+1]) ai[0]++;
}
int main()
{
    freopen("buylow.in","r",stdin);
    freopen("buylow.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<n;++i) scanf("%d",&a[i]);
    c[0]=a[0]; f[0]=size=1;
    int now;
    for(int i=1;i<n;++i){
        if(a[i]>=c[0]) now=0;
        else if(a[i]<c[size-1]) now=size++;
        else now=bsearch(c,a[i]);
        c[now]=a[i]; f[i]=now+1;
    }
    printf("%d ",size);
    for(int i=0;i<n;++i){
        memset(tot[i],0,sizeof(tot[i]));
        if(f[i]==1)
            tot[i][0]=tot[i][1]=1;
        else{
            tot[i][0]=1;
            now=-1;
            for(int j=i-1;j>=0;--j)
                if(f[j]+1==f[i]&&a[j]>a[i]&&now!=a[j]){
                    add(tot[i],tot[j]);
                    now=a[j];
                }
        }
    }
    now=-1;
    memset(ans,0,sizeof(ans));
    ans[0]=1;
    for(int i=n-1;i>=0;--i)
        if(f[i]==size&&now!=a[i]){
            add(ans,tot[i]);
            now=a[i];
        }
    printf("%d",ans[ans[0]]);
    for(int i=ans[0]-1;i>=1;--i) printf("%04d",ans[i]);
    printf("\n");
    return 0;
}

速度：
Executing...
   Test 1: TEST OK [0.000 secs, 3356 KB]
   Test 2: TEST OK [0.000 secs, 3356 KB]
   Test 3: TEST OK [0.000 secs, 3360 KB]
   Test 4: TEST OK [0.000 secs, 3360 KB]
   Test 5: TEST OK [0.000 secs, 3360 KB]
   Test 6: TEST OK [0.000 secs, 3356 KB]
   Test 7: TEST OK [0.000 secs, 3360 KB]
   Test 8: TEST OK [0.011 secs, 3360 KB]
   Test 9: TEST OK [0.011 secs, 3360 KB]
   Test 10: TEST OK [0.043 secs, 3360 KB]