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 }

为什么要离散化呢，因为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\n",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 }

巴特西

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

最新文章

热门文章