題意：?

求n個數(shù)中長度為m的上升子序列的個數(shù)?

解題思路：dp[i][j]表示第i個數(shù)長度為j的上升序列的個數(shù)。dp[i][j] = sum{dp[k][j-1] | a[k] < a[i]}，這里的時間復雜度有O(n3)，會超時，所以這里要有優(yōu)化。其實可以將a[i]離散化，對于每一個j，構造一個樹狀數(shù)組，這樣求sum{dp[k][j-1]}就可以用樹狀數(shù)組的求和了，時間復雜度可以降為O(n2logn)。

#include<iostream> #include<cstdio> #include<cstring> #include<set> #include<map> using namespace std;const int maxn = 1005; const int mod = 1e9+7; int n,m,dp[maxn][maxn]; int a[maxn],tree[maxn][maxn]; set<int> Set; map<int,int> Map;int lowbit(int x) {return x & -x; }void add(int i,int j,int c) {while(j <= n){tree[i][j] = (tree[i][j] + c) % mod;j += lowbit(j);} }int sum(int i,int j) {int ans = 0;while(j > 0){ans = (ans + tree[i][j]) % mod;j -= lowbit(j);}return ans; }int main() {int t,cas = 1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);Set.clear();Map.clear();for(int i = 1; i <= n; i++){scanf("%d",&a[i]);Set.insert(a[i]);}int cnt = 0;for(set<int>::iterator it = Set.begin(); it != Set.end(); it++)Map[*it] = ++cnt;memset(dp,0,sizeof(dp));memset(tree,0,sizeof(tree));for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){if(j == 1) dp[i][j] = 1;else dp[i][j] = (dp[i][j] + sum(j-1,Map[a[i]]-1)) % mod;add(j,Map[a[i]],dp[i][j]);}int ans = 0;for(int i = 1; i <= n; i++)ans = (ans + dp[i][m]) % mod;printf("Case #%d: %d\n",cas++,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5542（树状数组优化dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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