PKU3378 Crazy Thairs - 动态规划+树状数组

本文主要是介绍PKU3378 Crazy Thairs - 动态规划+树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给定一个长度为N的数字序列{ai}，问总共有多少个长度为5的上升子序列。（ai<10^9,N<=50000）

分析：

由于数字范围很大，首先将数字离散化为1~N之间的整数。原a[]数组转换为d[]数组，其中d[i]=j表示a[i]是a[]数组中第j小的数。

可以用动态规划来描述这个算法：

p从0到N，令i=d[p]。f[i][k]表示以数字i为结尾，长度为k的上升序列的个数。

f[i][k]+=∑f[j][k-1]（1<=j<i）

f[i][1]=1

这样的动态转移方程是可以求出正确解的，不过时间复杂度是O(n^2)。

这里可以用到树状数组来优化算法。可以看到在状态转移的时候要求的是1~i-1之间f[j][k-1]的和。正好满足树状数组应用的条件。修改f[i][k]的定义，使得它应用于树状数组。时间复杂度降为O(nlogn)

注意：1，最大的一组数据应该会超int64，所以要用大数计算。2，输入数据中ai可能出现相同元素，要注意处理。

 /*
PKU3378 Crazy Thairs
*/
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define clr(a) memset(a,0,sizeof(a)) 
#define int64 bignum_t 
#define N 50005 
/****************************************************/
#define DIGIT 4 //一个数组元素存放的位数个数 
#define DEPTH 10000 //DEPTH = 10DIGIT 
#define MAX 30 //数组的长度 
typedef int bignum_t[MAX+1];
//赋值  
void value(bignum_t a,char buf[]){
    char ch;
    int i,j;
    memset((void*)a,0,sizeof(bignum_t));
    
    for (a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)
        ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch;
    for (a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');
    for (i=1;i<=a[0];i++)
    for (a[i]=0,j=0;j<DIGIT;j++)
        a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0';
    for (;!a[a[0]]&&a[0]>1;a[0]--);
}
//输出 
void write(const bignum_t a){
    int i,j;
    for (printf("%d",a[i=a[0]]),i--;i;i--)
    for (j=DEPTH/10;j;j/=10)
        printf("%d",a[i]/j%10);
    puts("");
}
//加法 
void add(bignum_t a,const bignum_t b){//高精度数a+b,结果在a中 
    int i;
    for (i=1;i<=b[0];i++)
    if ((a[i]+=b[i])>=DEPTH)
    a[i]-=DEPTH,a[i+1]++;
    if (b[0]>=a[0])
    a[0]=b[0];
    else
    for (;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);
    a[0]+=(a[a[0]+1]>0);
}
/********************************************************/
int n,m;
int a[N],b[N],d[N];
int64 f[N][5];
int cmp(const void *i,const void *j){
    return a[*(int*)i]-a[*(int*)j];
}
void Add(int i,int j,int64 t){
    while(i<=m){
        add(f[i][j],t);
        i+=-i&i;
    }
}
void Sum(int i,int j,int64 s){
    char c0[10]="0";
    value(s,c0);
    while(i>0){
        add(s,f[i][j]);
        i-=-i&i;
    }
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        int i,j,k;
        //input 
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
            b[i]=i;
        }
        //order 
        qsort(b,n,sizeof(b[0]),cmp);
        m=1;
        d[b[0]]=1;
        for(i=1;i<n;i++){
            if(a[b[i]]!=a[b[i-1]]) m++;
            d[b[i]]=m;
        }
        //DP 
        int64 v1,t,u;
        char c0[10]="0";
        char c1[10]="1";
        value(v1,c1);
        for(k=0;k<=m;k++){  //clr 
            for(j=0;j<5;j++){
                value(f[k][j],c0);
            }
        }
        for(k=0;k<n;k++){   //DP 
            i=d[k];
            Add(i,0,v1);    //f[i][0]=1 
            for(j=1;j<=4;j++){
                Sum(i-1,j-1,t); //f[][j] t=Sum(i-1) 
                Add(i,j,t); //f[][j] Add(i,t) 
            }
        }
        //Total 
        int64 total;
        Sum(m,4,total);
        //output 
        write(total);
    }
    return 0;
}
 