HDU 5542 The Battle of Chibi（树状数组+dp）

The Battle of Chibi

Time Limit: 6000/4000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)

Total Submission(s): 1749    Accepted Submission(s): 621

Problem Description

Cao Cao made up a big army and was going to invade the whole South China. Yu Zhou was worried about it. He thought the only way to beat Cao Cao is to have a spy in Cao Cao's army. But all generals and soldiers of Cao Cao were loyal, it's impossible to convince any of them to betray Cao Cao.

So there is only one way left for Yu Zhou, send someone to fake surrender Cao Cao. Gai Huang was selected for this important mission. However, Cao Cao was not easy to believe others, so Gai Huang must leak some important information to Cao Cao before surrendering.

Yu Zhou discussed with Gai Huang and worked out 

N

 information to be leaked, in happening order. Each of the information was estimated to has

a

i

 value in Cao Cao's opinion.

Actually, if you leak information with strict increasing value could accelerate making Cao Cao believe you. So Gai Huang decided to leak exact

M

information with strict increasing value in happening order. In other words, Gai Huang will not change the order of the

N

 information and just select 

M

Input

T(1≤100)

.

T

 test cases follow.

Each test case begins with two numbers 

N(1≤N≤10

3

)

 and 

M(1≤M≤N)

, indicating the number of information and number of information Gai Huang will select. Then

N

 numbers in a line, the 

i

th

 number 

a

i

(1≤a

i

≤10

9

)

 indicates the value in Cao Cao's opinion of the 

i

th

Output

For each test case, output one line containing  Case #x: y, where  x

 is the test case number (starting from 1) and  y

 is the ways Gai Huang can select the information.

The result is too large, and you need to output the result mod by  1000000007(10

9

+7)

.

Sample Input

2 3 2 1 2 3 3 2 3 2 1

Sample Output

Hint

Source

The 2015 China Collegiate Programming Contest 

【解析】：

原本用dp退出来了一个状态方程，dp[i][j]表示以第j个元素结尾的长度为i的递增子序列数目（注意，包含第j元素）

如此实现的话：

dp[i][j]  +=  dp[i-1][t]，意思是当前状态来自：不包含第j元素，长度为i-1时的，所有符合a[t]<a[j]的，dp[i-1][t]的累加之和。

尝试着写了下，很遗憾需要三层循环维护，时间复杂度太高，注定超时。

for(int i=1;i<=m;i++)//长度   
       {  
        if(i==1)dp[i][j]=1;//长度为1时特殊处理   
        else  
           for(int j=i;j<=n;j++)//遍历元素   
           {  
            for(int t=1;t<j;t++)  
                if(a[t]<a[j])//累加前面的数目   
                    dp[i][j]+=dp[i-1][t];  
        }  
       }

然后带着这种思想，用树状数组把最里面那层循环优化掉，总复杂度变为O(n*n*log n)，给了4秒还是很险啊。

我用long long的数据提交时超时的，全改成int，竟然奇迹般的过了，耗时3556ms

这里有一个技巧，由于输入的数据最大10的9次方，所以需要在不改变原数据大小关系的基础上，降低数据大小。

   例如：1  4  7  4  9

可降为：1  2  3  2  4

使得树状数组的下标得以降低，不爆树状数组的下标

下面的代码中，用函数g()处理的，处理后存入数组t

【代码】：

#include <stdio.h>  
#include <stdlib.h>    
#include <string.h>    
#include <iostream>    
#include <algorithm>   
using namespace std;  
const int mod=1e9+7;  
struct node{  
    int id;  
    int a;  
}p[1200];  
int a[1200];  
int dp[1200][1200];  
int t[1200];  
int n,m;  
void add(int i,int k,int num)    
{      
    while(k<=n)    
    {      
        dp[i][k]+=num;  
        dp[i][k]%=mod;     
        k+=k&-k;  
    }      
}     
int read(int i,int k)//长度i时，1~k的区间和      
{      
    int sum=0;      
    while(k)      
    {      
        sum+=dp[i][k];   
        sum%=mod;     
        k-=k&-k;  //这里是逆序的，所以累减    
    }      
    return sum;      
}   
  
bool cmp(node f1,node f2)  
{  
    return f1.a<f2.a;  
}  
int g()  
{//p是结构体   
    for(int i=1;i<=n;i++)  
    {  
        p[i].a=a[i];//原数据   
        p[i].id=i;//记住下标   
    }  
    sort(p+1,p+n+1,cmp);//数组下标从1开始   
    int k=1;  
    for(int i=1;i<=n;i++)  
    {  
        if(i>1&&p[i].a!=p[i-1].a)k++;  
        t[p[i].id]=k;//不变序缩小原数据  
    }  
    return k;//缩距后最大数据  
}  
int main()  
{  
    int T,r=1;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%d%d",&n,&m);  
        memset(dp,0,sizeof(dp));  
        for(int i=1;i<=n;i++)  
            scanf("%d",a+i);  
        int k=g();//预处理t数组  
        for(int j=1;j<=n;j++)//加入第j个元素  
        {  
            for(int i=1;i<=j;i++)  
            {  
                if(i==1) add(i,t[j],1);  
                else  
                    add(i,t[j],read(i-1,t[j]-1));//把比t[j]小的累加进t[j]  
            }  
        }  
        int ans=read(m,n)%mod;  
        printf("Case #%d: %d\n",r++,ans);  
    }  
}