南阳ccpc C题 The Battle of Chibi 树状数组+dp

题目：

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

InputThe first line of the input gives the number of test cases, $T (1 \leq 100)$ OutputFor each test case, output one line containing Case #x: y, where $x$ Sample Input

Sample Output

Case #1: 3
Case #2: 0

Hint

In the first cases, Gai Huang need to leak 2 information out of 3. He could leak any 2 information as all the information value are in increasing order. 
In the second cases, Gai Huang has no choice as selecting any 2 information is not in increasing order.

题意：

给你n个有序的数，问你能找到多少个m长度的严格递增子序列

题解：

我们设dp[i][j]表示：截至于第i个数（使用了第i个数），所能构成的严格递增子序列长度为j的个数为dp[i][j]

那么dp[i][j]的值肯定是：dp[k][j-1]之和，k属于[1,i-1]。且要满足，那么输入的第k个数要小于第i个数才可以加上dp[k][j-1]

我们看数据n=1e3，如果暴力去写，复杂度就是O(n³)，所以我们肯定需要优化（我那时也不知道咋弄）

看其他题解发现，使用树状数组来优化，但是树状数组求得前缀和，而我们只是需要前缀和的一部分，这可怎么办。。

然后我们就可以处理一下输入，对于第k个数不小于第i个数的，我们可以先不处理它，那么这个dp[k][j-1]就是0

那么我们的前缀和相当于没有加上它，就可以达到满足我们的需要。这个处理只需要一个排序就可以

代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<map>
 6 #include<vector>
 7 #include<cstring>
 8 using namespace std;
 9 const int mod=1e9+7;
10 const int maxn=1e3+5;
11 #define mem(a) memset(a,0,sizeof(a))
12 //求sum(dp[1-x][j])
13 int n,m,dp[maxn][maxn];
14 struct shudui
15 {
16     int id,val;
17 }que[maxn];
18 bool cmp(shudui x,shudui y)
19 {
20     if(x.val!=y.val)
21         return x.val<y.val;
22     return x.id>y.id; //如果两个val相等，因为题目要求严格递增，所以这样排序就可以满足题意
23 }
24 int lowbit(int x)
25 {
26     return x&(-x);
27 }
28 void update(int x,int y,int val)  //更新包含dp[x][y]的
29 {   //后缀数组项
30     while(x<=n)
31     {
32         dp[x][y]=(dp[x][y]+val)%mod;
33         x+=lowbit(x);
34     }
35 }
36 int get_sum(int x,int y)
37 {
38     int sum=0;
39     while(x>0)
40     {
41         sum=(sum+dp[x][y])%mod;
42         x-=lowbit(x);
43     }
44     return sum;
45 }
46 int main()
47 {
48     int t,p=0;
49     scanf("%d",&t);
50     while(t--)
51     {
52         mem(dp);
53         scanf("%d%d",&n,&m);
54         for(int i=1;i<=n;++i)
55         {
56             scanf("%d",&que[i].val);
57             que[i].id=i;
58         }
59         sort(que+1,que+1+n,cmp);
60         for(int i=1;i<=n;++i)
61         {
62             for(int j=1;j<=m;++j)
63             {
64                 if(j==1)
65                     update(que[i].id,j,1);
66                 else //因为我们按照val排过序了，所以我们可以加上前缀和就行
67                 {
68                     int sum=get_sum(que[i].id-1,j-1);
69                     update(que[i].id,j,sum);
70                 }
71             }
72         }
73         printf("Case #%d: %d
",++p,get_sum(n,m));
74     }
75     return 0;
76 }