遞增子序列

金牌導(dǎo)航 數(shù)據(jù)結(jié)構(gòu)優(yōu)化DP-1

題目大意

給出一個(gè)序列，讓你求長度為m的單調(diào)遞增子序列的個(gè)數(shù)

輸入樣例

3 2 1 1 2 7 3 1 7 3 5 9 4 8

輸出樣例

2 12

數(shù)據(jù)范圍

$1?n?10^4,1?m?100,0?a_i?987654321$

解題思路

對(duì)于第i個(gè)數(shù)，如果要使以它結(jié)尾的單調(diào)遞增子序列長度為j，那么就要在前面找到比$a_i$小的數(shù)，累加以它們?yōu)榻Y(jié)尾長度為j-1的單調(diào)遞增序列（就是把i接到后面）
如果直接DP枚舉，會(huì)TLE
這時(shí)可以用樹狀數(shù)組在$O(logn)$的時(shí)間內(nèi)求出累加的值，沒計(jì)算出一個(gè)數(shù)，就加進(jìn)樹狀數(shù)組中

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 #define wyc 123456789//orz using namespace std; int n, m, l, x, a[N], b[N], c[101][N]; void add(int g, int x, int y) {for (; x <= l; x += x&-x)c[g][x] = (c[g][x] + y) % wyc; } int ask(int g, int x) {int y = 0;for (; x; x -= x&-x)y = (y + c[g][x]) % wyc;return y; } int main() {while(~scanf("%d%d", &n, &m)){memset(c, 0, sizeof(c));for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);b[i] = a[i];}sort(a + 1, a + 1 + n);l = unique(a + 1, a + 1 + n) - a - 1;//離散化for (int i = 1; i <= n; ++i){x = lower_bound(a + 1, a + 1 + l, b[i]) - a;for (int j = m; j > 1; --j)add(j, x, ask(j - 1, x - 1));//求累加值，再加到樹狀數(shù)組中add(1, x, 1);}printf("%d\n", ask(m, l));}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【树状数组】递增子序列（金牌导航 数据结构优化DP-1）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。