【一级讲解】非递减子序列数目

不同子序列

题意:输入一个只包含小写字母的字符串,求不同的非递减子序列的数量.

---

问题分析：

解法一：

抱歉，又是一道残缺题目，未公开原题，一些数据范围和示例不得而知，但还是不妨碍思考基本算法的。其实看到这个题目，我就想起了我之前写过的最长递增子序列——一维动态规划，算法是一模一样的，就认为他的数据范围比较小吧，不考虑复杂度过大超时的情况，再经过简单的数学推导就可以知道答案啦~代码和推论如下

已知一个集合有n个元素，则它的子集有2^{n个，真子集有2}N-1个，非空子集也为2^N-1

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string a; 
    int dp[100001];
    int i,j;
    
    cin >> a;
    
    for ( i=0; i<a.length(); i++ )
        dp[i] = 1;
    
    for ( j=1; j<a.length(); j++ )
        for ( i=0; i<j; i++ )
            if ( a[j]>=a[i] && dp[j]<dp[i]+1 )
                dp[j] = dp[i]+1;
    
    int max = 0;            
    for ( i=0; i<a.length(); i++ )
        if ( dp[i]>max ) max = dp[i]; 
                
    int ans = ((int)(pow(2,max)-1));
    cout<<ans; 
}

解法二：

这里再用下ACM协会技术部林振杰在公开课上的PPT，用的是维护的思想，和DP的思想有点点类似，但这里就减少了判断大小了（因为就26个字母，在ASCII中又是默认升序的），把复杂度降低到了O(N)

---

进阶篇：

题源：HDU2227

Find the nondecreasing subsequences

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2451 Accepted Submission(s): 943
*

Problem Description

How many nondecreasing subsequences can you find in the sequence S = {s1, s2, s3, …, sn} ? For example, we assume that S = {1, 2, 3}, and you can find seven nondecreasing subsequences, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}.

Input

The input consists of multiple test cases. Each case begins with a line containing a positive integer n that is the length of the sequence S, the next line contains n integers {s1, s2, s3, …, sn}, 1 <= n <= 100000, 0 <= si <= 2^31.

Output

For each test case, output one line containing the number of nondecreasing subsequences you can find from the sequence S, the answer should % 1000000007.

Sample Input

3
1 2 3

Sample Output

7

挖个小坑：

一开始我也是用DP的方法的，代码如下

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int a[100001]; 
    int dp[100001];
    int i,j;
    
    int n;
    cin >> n;
    
    for ( i=0; i<n; i++ )
        cin >> a[i];
    
    for ( i=0; i<n; i++ )
        dp[i] = 1;
    
    for ( j=1; j<n; j++ )
        for ( i=0; i<j; i++ )
            if ( a[j]>a[i] && dp[j]<dp[i]+1 )
                dp[j] = dp[i]+1;
    
    int max = 0;            
    for ( i=0; i<n; i++ )
        if ( dp[i]>max ) max = dp[i]; 
                
    int ans = ((int)(pow(2,max)-1)%1000000007);
    cout<<ans; 
}

但最后提交上去果然不出所料…超时了!
因为我用到了二重for循环，复杂度为O(N^2)，想了许久都想不出如何用其他算法降低复杂度。

看了一圈网上的相关题解后，发现大多数都是用树状数组+离散AC的

但…这远远超出了我现在的知识范围，故现在先挖一个坑，21寒假一定回来补hhh（应该也许会记得）