题目

传送门：QWQ

分析

题意：给个数列，求有多少五元上升组

考虑简化一下问题：如果题目求二元上升组怎么做。

仿照一下逆序对，用树状数组维护一下就ok了。

三元怎么做呢？

把二元的拓展一位就可以了，即把第三个也扔进树状数组

所以这题就渐渐明朗了：

用$ dp[i][x] $表示以$ A[x] $结尾的$ x $元上升组有多少个

那么：

$ dp[i][x]=\sum_{j=1}^{i-1} dp[j][x-1] (A[j]<A[i]) $

其中 $ dp[i][1]=1 $

因为多了一位大的就加了一位嘛

但这个看起来是$ O(n^2) $的，肯定要凉，所以扔进树状数组优化一下。

对了，这题还要离散化和高精度

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int maxn=,N = , Base = ;

typedef long long LL;

class BigNum {

public:

    int num[], len;

    BigNum():len() {}

    BigNum(int n):len() {   for( ; n > ; n /= Base) num[len++] = n%Base;   }

    BigNum Bigvalueof(LL n) {

        len = ;   while(n) {   num[len++] = n%Base;   n /= Base;   }

        return *this;

    }

    BigNum operator + (const BigNum& b) {

        BigNum c;   int i, carry = ;

        for(i = ; i < this->len || i < b.len || carry > ; ++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;

    }

    BigNum operator += (const BigNum& b) {  *this = *this + b;   return *this;   }

    void Print() {

        if(len == )    {puts(""); return ;}

        printf("%d", num[len - ]);

        for(int i = len - ; i >= ; --i)

            for(int j = Base/; j > ; j /= )

                printf("%d", num[i]/j%);

        puts("");

    }

};

typedef BigNum bign;

int n;

bign sum[maxn][];

struct Node{

    int v,pos;

    bool operator < (const Node& a) const{ return v<a.v; }

}a[maxn];

void add(int x,int e,bign a){for(;x<=n;x+=x&-x)sum[x][e]+=a;}

bign summ(int x,int e){bign ans;for(;x>;x-=x&-x)ans+=sum[x][e];return ans;}

int main(){

    while(~scanf("%d",&n)){

        for(int i=;i<=n;i++){scanf("%d",&a[i].v);a[i].pos=i;}

        sort(a+,a++n); memset(sum,,sizeof(sum));

        int cnt=;

        bign ans=;

        for(int i=;i<=n;i++){

            add(a[i].pos,,);

            for(int j=;j<=;j++){

                add(a[i].pos,j,summ(a[i].pos-,j-));

            }

        }

        summ(n,).Print();

    }

    return ;

}

巴特西

【POJ】3378 Crazy Thairs（树状数组+dp+高精）

题目

传送门：QWQ

分析

代码

最新文章

热门文章