【NOIP TG咕咕咕咕咕】P1108 低价购买+P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower 题解 PART 2

· · 题解

【NOIP TG咕咕咕咕咕】P1108 低价购买+P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower 题解 PART 2
PART 2 讲讲升级版：P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower
不妨假设第二问答案是由C(1,n)+C(2,n)+...+C(n,n)组成
也就是假设所有数字一样（当然，答案会是一，但是为了方便考虑上界我们就假设是算本质不同的最长不上升子序列）
简化计算，我们令C(n/2,n)为上界
带入n=5000，答案上界为C(2500,5000)
最多10000位（瞎算），long long轻松被卡

（以上全部瞎算）
我们可以考虑两种解决方法

1 DOUBLE!

用double类型存储答案/10^15的值，最后乘回来即可
100分

2 面向数据编程

小心棕名

3 毒瘤高精

也是正解之一
只需写高精加即可
小代码： 

#include<bits/stdc++.h>
using namespace std;
struct huge_int{
    int len;
    int a[1000];
};
const int N=5005;
int n;
int a[N]; 
int f[N];
huge_int g[N],ans;
int maxn=1;
void print(huge_int x){
    for(int i=x.len;i>=1;i--) printf("%d",x.a[i]);
    printf("\n"); 
}
huge_int add(huge_int x,huge_int y){
    //printf("***********\n");
    //print(x);
    //print(y);
    for(int i=x.len+1;i<=100;i++) x.a[i]=0;
    for(int i=y.len+1;i<=100;i++) y.a[i]=0;
    huge_int z;
    z.len=max(x.len,y.len);
    memset(z.a,0,sizeof(z.a));
    for(int i=1;i<=z.len;i++){
        z.a[i]=z.a[i]+x.a[i]+y.a[i];
        z.a[i+1]=z.a[i]/10;
        z.a[i]=z.a[i]%10;
    //  cout<<x.a[i]<<" "<<y.a[i]<<" "<<z.a[i]<<endl;
    }
    if(z.a[z.len+1]>0) z.len++;
//  print(z);
    //printf("***********\n");
    return z; 
}

void Subtask2(){//biantai第二问
    for(int i=1;i<=n;i++) memset(g[i].a,0,sizeof(g[i].a));
    memset(ans.a,0,sizeof(ans.a));
    g[1].len=1,g[1].a[1]=1;
    ans.len=1,ans.a[1]=0;
    for(int i=2;i<=n;i++){
        g[i].len=1,g[i].a[1]=0;
        for(int j=1;j<i;j++){
            if(a[i]==a[j]&&f[i]==f[j]) g[j].len=1,g[j].a[1]=0;
            else if(a[i]<a[j]&&f[i]==f[j]+1) g[i]=add(g[i],g[j]);
        }
        if(g[i].len==1&&g[i].a[1]==0) g[i].a[1]=1;
    }
    for(int i=1;i<=n;i++){
        if(f[i]==maxn) ans=add(ans,g[i]);
    }
    print(ans);
}
void Subtask1(){//常规第一问 
    memset(f,0,sizeof(f));
    f[1]=1;
    for(int i=2;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++){
            if(a[i]<a[j]&&f[j]+1>f[i]) f[i]=f[j]+1; 
        }
        maxn=max(maxn,f[i]);
    }
    printf("%d ",maxn);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    Subtask1();
    Subtask2(); 
    return  0;
}

4 毒瘤高精+压位

我们发现程序部分有NlogN的做法。毒瘤一点的出题人会卡一般的高精
用压位可以快好多

5 毒瘤高精+FFT

瞎写的，我不会