摘要：
当时比赛时超时了，那时没学过树状数组，也不知道啥叫离散化。今天刚学树状数组还不太会用。下面给出树状数组的模板1intbit[MAX_N+1],n;2intsum3{4ints=0;5while(i˃0)6{7s+=bit[i];8i-=i&-i;9}10returns;11}121314voidadd15{16while17{18bit[i]+=x;19i+=i&-i;20}21}ViewCode为什么要离散化呢，因为N的范围为1000，而所给元素a[i]的范围为1e+9;用树状数组时开不了那么大的数组，所以要离散化，将所给的数对应到1000以内连续的数，这样不会改变每个数之间的大小关系。=b[j-1])46{47cnt++;48my[b[j]]=cnt;49}50else51{52my[b[j]]=cnt;53}54}55}56for57{58a[j]=my[a[j]];59}//将原数组每个元素改为对应元素200100300-〉21360for//要选的个数61{62memset;63for//可以改成从1循不过时间长64{65llnn=sum;66dp[j][k]=nn;67add;68}69}70llendd=0;71for72{73endd=%pp;74}75printf;76printf;77}78return0;79}80llsum81{82lls=0;83while(n˃0)84{85s=%pp;86n=n&(n-1);87}88returns;89}90voidadd91{92while93{94bit[n]=%pp;95n+=;96}97}
当时比赛时超时了，那时没学过树状数组，也不知道啥叫离散化（貌似好像现在也不懂）。百度百科——离散化，把无限空间中无限的个体映射到有限的空间中去，以此提高算法的时空效率。
这道题是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(inti) 3 { 4 int s=0; 5 while(i>0) 6 { 7 s+=bit[i]; 8 i-=i&-i; 9 } 10 returns; 11 } 12 13 14 void add(int i,intx) 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]；最后复杂度为n2log(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 longll; 8 ll sum(intn); 9 void add(int n,ll kk,intz); 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 namespacestd; 16 int main(void) 17 { 18 intn,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(intn) 81 { 82 ll s=0; 83 while(n>0) 84 { 85 s=(bit[n]+s)%pp; 86 n=n&(n-1); 87 } 88 returns; 89 } 90 void add(int n,ll kk,intz) 91 { 92 while(n<=z) 93 { 94 bit[n]=(kk+bit[n])%pp; 95 n+=(n&(-n)); 96 } 97 }