HDU2227Find the nondecreasing subsequences（树状数组+DP）

题目大意就是说帮你给出一个序列a，让你求出它的非递减序列有多少个。

设dp[i]表示以a[i]结尾的非递减子序列的个数，由题意我们可以写出状态转移方程：

dp[i] = sum{dp[j] | 1<=j<i && a[j] <= a[i]} + 1.

这样一来这里面所有的dp[]值的和就是最后的结果。

但是这个状态转移方程很明显复杂度是O(n^2),但是n可以达到100000，很明显会超时。既然是求前导和，很明显我们就应该可以想到用树状数组（虽然我怎么也不可能想到==！）,这样一来那么复杂度就可以降到O(nlogn)。

那么怎么求前导和呢？？也并不是所有的dp[j](1<=j<i)都要被加进去啊，只有满足a[j]<=a[i]时dp值才可以被计算在内。。。

解决办法就是先将原数组复制一份，然后排序，然后再按照原顺序找出每一个数的排序后的所在位置，然后计算这个位置的dp[]值，可以通过一例看出他的正确性：

原数组： 8 5 3 4 1

排序后： 1 3 4 5 8

可以看出原数组的每一个数对应到排序后的下标就是：5 4 2 3 1

没有计算前，树状数组里的值全为0，然后

1、找到8的位置,并计算以‘8’结尾的dp[]的值，也就是计算‘8’在排序后所在位置5的值，计算dp[5] = 0 + 1 = 1

2、然后找到‘5’在排序后的位置4，由于‘8’>‘5’,所以以‘5’结尾的dp值应该也是1，正好排序后‘5’在第4个，在‘8’前面，自然dp[4]计算出来还是1

3、同理，‘3’出现在第二个，dp[2] = 1

4、然后到‘4’，他在排序后出现在第3 个，而原数组中‘4’之前有一个数‘3’，所以计算出来以‘4’结尾的dp[]值应该就是以‘3’结尾的dp值+1等于2，而我们看排序后4出现在第3个，而第3个之前又正好有一个dp[2]=1已经被计算出来了，这样dp值的前导和就是1，从而dp[3] = dp[2] + 1 = 2.

5、最后dp[1] = 1.所以最后结果就是1+1+1+2+1 = 6

其实上面的排序找到下标就是为了保证每个数计算出来的值都是满足a[j] < a[i]时，所计算出来的dp值。这也就是原题的解。

而要实现找到原数组在排序后的位置，我们只需要二分查找就可以了，又因为原数组可能会有相同的数，为了找到的是同一个标号，所以需要二分查找下限（或者上限）。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define mem(a) memset(a,0,sizeof(a))

 #define mod 1000000007

 #define MAXN  100010

 int num[MAXN], d[MAXN], N, DP[MAXN];

 int lowbit(int x)

 {

     return x & -x;

 }

 int getSum(int k)

 {

     int ans = ;

     while(k>=)

     {

         ans = (ans + DP[k]) % mod;

         k -= lowbit(k);

     }

     return ans;

 }

 void edit(int k,int val)

 {

     while(k<=N)

     {

         DP[k] = (DP[k] + val) % mod;

         k += lowbit(k);

     }

 }

 int bsearch(int num)

 {

     int x = , y = N+, mid;

     while(y > x )

     {

         mid = (x+y)/;

         if(d[mid] == num && d[mid-]<num) return mid;

         if(d[mid] >= num) y = mid;

         else x = mid+;

     }

     return mid;

 }

 int main()

 {

     while(~scanf("%d", &N))

     {

         mem(DP);

         mem(d);  mem(num);

         for(int i = ; i <= N; i ++)

         {

             scanf("%d", &num[i]);

             d[i] = num[i];

         }

         sort(d+, d+N+);

         for(int i=;i<=N;i++)

         {

             int id = bsearch(num[i]);

             edit(id, getSum(id)+);

         }

         printf("%d\n", getSum(N));

     }

     return ;

 }

巴特西

HDU2227Find the nondecreasing subsequences（树状数组+DP）

最新文章

热门文章