POJ3378 Crazy Thairs(树状数组+dp+高精度)

一道经典的树状数组老题，从题目中我们看出要求五元递增组，而普通树状数组只能求二元，我们我们考虑开五维树状数组来求取

例如 tr[3][x],就代表以x为结尾的三元递增组

for(i=1;i<=n;i++){
            int pos=find(a[i]);
            add(1,pos,1);
            for(int j=2;j<=5;j++)
            add(j,pos,sum(j-1,pos-1));
        }

这是核心代码，对于每个数，先将他插在第一维，然后对剩下几维继续dp叠加，add中代表的第几维，在哪个位置，插入前一维前缀和

本题数据大，要离散化，另外因为答案过大超过long long ，只要贴一个高精度模板即可。

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
const int N =1e5+10;
const int base =10000;
vector<int> num;
class bigint{
    public:
        int num[7],len;
        bigint():len(0){}
        bigint(int n):len(0){
            for(;n>0;n/=base)
            num[len++]=n%base;
        }
        bigint bigvalue(ll n){
            len=0;
            while(n){
                num[len++]=n%base;
                len/=base;
            }
            return *this; 
        }
        bigint operator +(const bigint &b){
            bigint c;
            int i;
            int carry=0;
            for(i=0;i<this->len||i<b.len||carry>0;i++){
                if(i<this->len)
                carry+=this->num[i];
                if(i<b.len) carry+=b.num[i];
                c.num[i]=carry%base;
                carry/=base;
            }
            c.len=i;
            return c;
        }
        bigint operator +=(const bigint &b){
            *this=*this+b;
            return *this;
        }
        void print(){
            if(len==0){
                cout<<0<<endl;
                return ;
            }
            printf("%d",num[len-1]);
            for(int i=len-2;i>=0;i--)
            for(int j=base/10;j>0;j/=10){
                printf("%d",num[i]/j%10);
            }
            
        }
};
typedef bigint big;
int a[N];
bigint tr[6][N];
int n;
int lowbit(int x){
    return x&-x;
}
big sum(int x,int pos){
    int i;
    big res=0;
    for(i=pos;i;i-=lowbit(i)){
        res=res+tr[x][i];
    }
    return res;
}
void add(int pos,int x,big v){
    int i;
    for(i=x;i<=n;i+=lowbit(i)){
        tr[pos][i]=tr[pos][i]+v;
    }
}
int find(int x){
    return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
int main(){
    while(cin>>n){
        int i;
        num.clear();
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            num.push_back(a[i]);
        }
        sort(num.begin(),num.end());
        num.erase(unique(num.begin(),num.end()),num.end());
          memset(tr,0,sizeof tr);
        for(i=1;i<=n;i++){
            int pos=find(a[i]);
            add(1,pos,1);
            for(int j=2;j<=5;j++)
            add(j,pos,sum(j-1,pos-1));
        }
        sum(5,n).print();
    }
}

View Code

POJ3378 Crazy Thairs(树状数组+dp+高精度)

推荐阅读