HDU 5542 The Battle of Chibi（dp+树状数组）

梦里梦外; 2021-11-30 00:24 182阅读 0赞

## 题意：给出长度为n的序列，问这个序列中有多少个长度为m的单调递增子序列。 ##

## 分析：《算法竞赛进阶指南》P312-313。 ##

## 代码： ##

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 1006, INF = 0x3f3f3f3f, P = 1000000007;
    int n, m, a[N], b[N], c[N], f[N][N], num;
    
    void add(int x, int y) {
    	while (x <= n + 1) {
    		c[x] = (c[x] + y) % P;
    		x += x & -x;
    	}
    }
    
    int ask(int x) {
    	int ans = 0;
    	while (x) {
    		ans = (ans + c[x]) % P;
    		x -= x & -x;
    	}
    	return ans;
    }
    
    void The_Battle_of_Chibi() {
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    	memcpy(b, a, sizeof(b));
    	sort(b + 1, b + n + 1);
    	for (int i = 1; i <= n; i++)
    		a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b + 1;
    	a[0] = f[0][0] = 1;
    	for (int i = 1; i <= m; i++) {
    		memset(c, 0, sizeof(c));
    		add(1, f[i-1][0]);
    		for (int j = 1; j <= n; j++) {
    			f[i][j] = ask(a[j] - 1);
    			add(a[j], f[i-1][j]);
    		}
    	}
    	int ans = 0;
    	for (int i = 1; i <= n; i++) ans = (ans + f[m][i]) % P;
    	printf("Case #%d: %d\n", ++num, ans);
    }
    
    int main() {
    	int t;
    	cin >> t;
    	while (t--) The_Battle_of_Chibi();
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关树状数组 Color the ball

Color the ball Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja

﹏ヽ暗。殇╰゛Y/ 2024年01月11日 07:45/ 0 赞/ 62 阅读

相关【树状数组】【2019hdu多校】Find the answer

题意：每次从1到i-1中选择最少的数减为0，确保1到i的前缀和小于m，我们离散化，从小到大排序，按照输入顺序每遍历一个就插入到树状数组在排序过后的位置，二分位置确保树状数组的前

客官°小女子只卖身不卖艺/ 2023年06月01日 08:46/ 0 赞/ 17 阅读

相关 HDU 1166(线段树；树状数组)

题意：如题。树状数组： include <cstdio> include <cstring> include <algorithm>

分手后的思念是犯贱/ 2022年09月20日 11:22/ 0 赞/ 219 阅读

相关 HDU 1556-Color the ball（树状数组-区间修改单点查询）

Color the ball Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja

以你之姓@/ 2022年08月21日 15:00/ 0 赞/ 198 阅读

相关 hdu 1166 敌兵布阵(树状数组)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

雨点打透心脏的1/2处/ 2022年07月16日 13:18/ 0 赞/ 157 阅读

相关 HDU 1541 Stars（树状数组||线段树）

Astronomers often examine star maps where stars are represented by points on a plane and

爱被打了一巴掌/ 2022年06月12日 00:20/ 0 赞/ 241 阅读

相关 HDU 5493 Queue（树状数组+二分）

N N people numbered from 1 to N N are waiting in a bank for service. They all stand in a

灰太狼/ 2022年06月08日 02:59/ 0 赞/ 189 阅读

相关 HDU - 5517 Triple(二维树状数组)

原文:http://blog.csdn.net/beihai2013/article/details/49588259 [点我看题][Link 1] 题意：有二元组

电玩女神/ 2022年06月06日 23:46/ 0 赞/ 191 阅读

相关 HDU 5542 The Battle of Chibi（dp+树状数组）

题意：给出长度为n的序列，问这个序列中有多少个长度为m的单调递增子序列。分析：《算法竞赛进阶指南》P312-313。代码： include <cs

梦里梦外;/ 2021年11月30日 00:24/ 0 赞/ 183 阅读

相关树状数组 hdu2689 hdu2838

题意：给定一个正整数n，和一个1-n的一个排列，每个数可以和旁边的两个数的任意一个交换，每交换一次总次数就要加一，问将这个排列转换成一个递增的排列需要多少次交换？题意可以转

快来打我*/ 2021年11月01日 03:38/ 0 赞/ 314 阅读