盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 4991 Ordered Subsequence(LIS+树状数组)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4991

题意

给定一个长度为N的序列,问所有长度为M的上升子序列的个数

思路

另dp[i][j]表示以a[i]为结尾,长度为j的上升子序列的个数,有如下转移方程
dp[i][j] = sum(dp[k][j - 1]) 其中k小于i,且a[k]<a[i]
朴素的转移是n2m,可以通过树状数组来维护和,复杂度降到nm*log(n)

取模真心慢。。2s左右的代码,把取模改成减直接300+ms就过了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 10005;
int n, m, a[N], b[N];
int s[105][N];
int mod = 123456789;
int lowbit(int x) {
return x & (-x);
}
void add(int x, int v, int id) {
while(x <= n) {
s[id][x] += v;
if (s[id][x] >= mod) s[id][x] -= mod;
x += lowbit(x);
}
}
ll sum(int x, int id) {
ll res = 0;
while(x) {
res += s[id][x];
if (res >= mod) res -= mod;
x -= lowbit(x);
}
return res;
}
int main () {
while(~scanf("%d%d", &n, &m)) {
for (int i = 0; i < n; i++) scanf("%d", a + i), b[i] = a[i];
sort(b, b + n);
int t = unique(b, b + n) - b;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++) s[j][i] = 0;
ll ans = 0;
for (int i = 0; i < n; i++) {
int pos = lower_bound(b, b + t, a[i]) - b + 1;
add(pos, 1, 1);
for (int j = 2; j <= m; j++) {
ll tmp = sum(pos - 1, j - 1);
if (!tmp) break;
add(pos, tmp, j);
}
}
ans = sum(t, m);
printf("%I64d\n", ans);
}
return 0;
}