本文主要是介绍HDU 4991 Ordered Subsequence（dp+树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
好题啊。 自己想的dp。
dp【i】【j】 代表第i个数时 递增长度为 j 的个数。
明显 d【i】【j】 = sum（d【k】【j-1】 && num【k】 < num【i】）
但是写暴力的话 需要三层循环 n^2*k 的复杂度。 肯定超时。
递推公式有个特点。 到达每一项之后 都是前面项数的和。 所以需要用树状数组优化。（正好是求前缀和）
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAXN 10000+10
#define INF (1<<30)
#define mod 123456789
int c[MAXN];
int n,k;
int lowbit(int x)
{return x & (-x);
}void update(int pos,LL val)
{while(pos <= n){c[pos] = (c[pos]+ val)%mod;pos += lowbit(pos);}
}LL Sum(int pos)
{LL res = 0;while(pos > 0){res = (res+c[pos])%mod;pos -= lowbit(pos);}return res;
}
LL d[MAXN][101];
LL a[MAXN];
LL b[MAXN];
int main (){while(scanf("%d%d",&n,&k) != EOF){for(int i = 1; i <= n; i++){scanf("%I64d",&a[i]);b[i] = a[i];}memset(d,0,sizeof(d));for(int i = 1; i <= n; i++){d[i][1] = 1;}sort(b+1,b+1+n);LL ans = 0;for(int i = 2; i <= k; i++){memset(c,0,sizeof(c));for(int j = 1; j <= n; j++){int id = lower_bound(b+1,b+1+n,a[j]) - (b); // 自己的编号(相当于离散化，因为数据原本很大，这样可以缩小到1-10000)d[j][i] = Sum(id-1); // 求 小于 a[j] 的 所有数 长度为 i-1的和。update(id,d[j][i-1]); // 把 c 数组的 id位置更新成 d[j][i-1] 以便于 下一个 数字的时候 求和}}LL sum = 0;for(int j = 1; j <= n; j++){sum = (sum+d[j][k])%mod;}printf("%I64d\n",sum);}return 0;
}
这篇关于HDU 4991 Ordered Subsequence（dp+树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
