The 2015 China Collegiate Programming Contest -ccpc-c题-The Battle of Chibi（hdu5542）（树状数组，离散化）

当时比赛时超时了，那时没学过树状数组，也不知道啥叫离散化（貌似好像现在也不懂）。百度百科——离散化，把无限空间中无限的个体映射到有限的空间中去，以此提高算法的时空效率。

这道题是dp题，离散化和树状数组用来优化，状态转移方程：dp[i][j]=sum(dp[i-1][k])----k需要满足a[j]>a[k]&&k<j;

i表示所要选的个数，j表示以第a[j]个数结尾所有的符合要求的递增串的个数，最后答案就是sum(dp[n][j])--1<=j<=p;n 为要选的个数，p为所给数的总数，这个方程很容易想，这里不说了

（因为叫我说也说不清）。

数据肯定很大所以题目要求取模。

今天刚学树状数组还不太会用。

下面给出树状数组的模板

 1 int bit[MAX_N+1],n;
 2 int sum(int i)
 3 {
 4     int s=0;
 5     while(i>0)
 6     {
 7         s+=bit[i];
 8         i-=i&-i;
 9     }
10     return s;
11 }
12 
13 
14 void add(int i,int x)
15 {
16     while(i<=n)
17     {
18         bit[i]+=x;
19         i+=i&-i;
20     }
21 }

View Code

为什么要离散化呢，因为N的范围为1000，而所给元素a[i]的范围为1e+9;

用树状数组时开不了那么大的数组，所以要离散化，将所给的数对应到1000以内连续的数，这样不会改变每个数之间的大小关系。

那么树状数组就可以开bit[1005]；最后复杂度为n²log(n);

下面给出代码

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 #include<iostream>
 6 #include<map>
 7 typedef long long ll;
 8 ll sum(int n);
 9 void add(int n,ll kk,int z);
10 ll dp[1005][1005];
11 int a[1005];
12 int b[1005];
13 int bit[1005];//树状数组
14 const ll pp=1e9+7;
15 using namespace std;
16 int main(void)
17 {
18     int n,i,j,k,p,q;
19     scanf("%d",&n);
20     for(i=1; i<=n; i++)
21     {
22         map<int,int>my;//用来离散化的（将大的数转化1000以内的数）
23         memset(dp,0,sizeof(dp));
24         for(j=0; j<=1000; j++)
25         {
26             dp[1][j]=1;
27         }//当就选1个时全初始化1
28         scanf("%d %d",&p,&q);
29         for(j=1; j<=p; j++)
30         {
31             scanf("%d",&a[j]);
32             b[j]=a[j];
33         }
34         sort(b+1,b+p+1);//离散化前的排序比如200 300 100 排完为100 200 300 那么对应为1 2 3 
35         int c[1005];
36         int cnt=1;
37         for(j=1; j<=p; j++)
38         {
39             if(j==1)
40             {
41                 my[b[j]]=cnt;
42             }
43             else
44             {
45                 if(b[j]!=b[j-1])
46                 {
47                     cnt++;
48                     my[b[j]]=cnt;
49                 }
50                 else
51                 {
52                     my[b[j]]=cnt;
53                 }
54             }
55         }
56         for(j=1; j<=p; j++)
57         {
58             a[j]=my[a[j]];
59         }//将原数组每个元素改为对应元素 200 100 300 -〉2 1 3
60         for(j=2; j<=q; j++)//要选的个数
61         {
62             memset(bit,0,sizeof(bit));
63             for(k=j-1; k<=p; k++)//可以改成从1循不过时间长
64             {
65                 ll nn=sum(a[k]-1);
66                 dp[j][k]=nn;
67                 add(a[k],dp[j-1][k],cnt);
68             }
69         }
70         ll endd=0;
71         for(j=1; j<=p; j++)
72         {
73             endd=(endd+dp[q][j])%pp;
74         }
75         printf("Case #%d: ",i);
76         printf("%lld
",endd);
77     }
78     return 0;
79 }
80 ll sum(int n)
81 {
82     ll s=0;
83     while(n>0)
84     {
85         s=(bit[n]+s)%pp;
86         n=n&(n-1);
87     }
88     return s;
89 }
90 void add(int n,ll kk,int z)
91 {
92     while(n<=z)
93     {
94         bit[n]=(kk+bit[n])%pp;
95         n+=(n&(-n));
96     }
97 }

油！油！you@