首页 > 代码库 > HDU 4990 Ordered Subsequence --数据结构优化DP
HDU 4990 Ordered Subsequence --数据结构优化DP
题意：给一串数字，问长度为m的严格上升子序列有多少个
解法：首先可以离散化为10000以内，再进行dp，令dp[i][j]为以第i个元素结尾的长度为j的上升子序列的个数，
则有dp[i][j] = SUM(dp[k][j-1]) (a[k] < a[i] && k < i)
不可能直接遍历，所以考虑优化，可以看出dp方程相当于一个区间求和，所以可以用树状数组来优化。
代码：
#include <iostream>#include <cmath>#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#define SMod 123456789#define lll __int64using namespace std;#define N 10007lll c[N],a[N],b[N];int n,m;lll dp[N][104];int lowbit(int x){ return x & (-x);}void modify(int pos,lll val){ while(pos <= n) { c[pos] += val; pos += lowbit(pos); }}lll getsum(int pos){ lll res = 0; while(pos > 0) { res = (res+c[pos])%SMod; pos -= lowbit(pos); } return res;}int main(){ int i,j; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) { scanf("%I64d",&a[i]); b[i] = a[i]; } sort(b+1,b+n+1); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) dp[i][1] = 1; for(j=2;j<=m;j++) { memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { int ind = lower_bound(b+1,b+n+1,a[i])-b; dp[i][j] = getsum(ind-1); modify(ind,dp[i][j-1]); } } lll ans = 0; for(i=1;i<=n;i++) ans = (ans + dp[i][m])%SMod; printf("%I64d\n",ans); } return 0;}
HDU 4990 Ordered Subsequence --数据结构优化DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。