[HDOJ5542]The Battle of Chibi（DP 树状数组）

题目链接：http://acm./showproblem.php?pid=5542

题意：n个数中找m个数，使得从左到右读是上升的子序列。问一共有多少种。

dp(i,j)表示取到第i个位置，长为j并且最后一个数为a(i)的方案总数。

更新就比较容易了，dp(i,j)=∑(k=1->j-1)dp(i-1,k)，初始化dp(i,1)=1。

1 #include <bits/stdc++.h> 2 using namespace std; 3 #define lowbit(x) x & (-x) 4 5 const int mod = int(1e9+7); 6 const int maxn = 1010; 7 int dp[maxn][maxn]; 8 int a[maxn], h[maxn]; 9 int n, m, hcnt;10 11 int sum(int i, int x) {12int ret = 0;13while(x) {14 ret = (ret + dp[i][x]) % mod;15 x -= lowbit(x);16}17return ret;18 }19 20 void update(int i, int x, int k) {21while(x <= n) {22 dp[i][x] = (dp[i][x] + k) % mod;23 x += lowbit(x);24}25 }26 27 int getid(int x) {28return lower_bound(h, h+hcnt, x) - h;29 }30 31 int main() {32//freopen("in", "r", stdin);33int T, _ = 1;34scanf("%d", &T);35while(T--) {36 printf("Case #%d: ", _++);37 scanf("%d %d", &n, &m);38 for(int i = 1; i <= n; i++) {39 scanf("%d", &a[i]);40 h[i-1] = a[i];41 }42 sort(h, h+n); hcnt = unique(h, h+n) - h;43 for(int i = 1; i <= n; i++) a[i] = getid(a[i]) + 1;44 memset(dp, 0, sizeof(dp));45 for(int i = 1; i <= n; i++) {46 for(int j = 1; j <= m; j++) {47 if(j == 1) {48 update(j, a[i], 1);49 continue;50 }51 int tmp = sum(j-1, a[i]-1);52 update(j, a[i], tmp);53 }54 }55 printf("%d\n", sum(m, n));56}57return 0;58 }