1202 子序列个数(DP)-白红宇

1202 子序列个数(DP)

阅读量：7029 次

发布时间：2019-06-28

本文共 1424 字，大约阅读时间需要 4 分钟。

题目来源：

基准时间限制：1 秒空间限制：131072 KB 分值: 40

子序列的定义：对于一个序列a=a[1],a[2],......a[n]。则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1<=p1<p2<.....<pm<=n。

例如4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。对于给出序列a，有些子序列可能是相同的，这里只算做1个，请输出a的不同子序列的数量。由于答案比较大，输出Mod 10^9 + 7的结果即可。

Input

第1行：一个数N，表示序列的长度(1 <= N <= 100000)第2 - N + 1行：序列中的元素(1 <= a[i] <= 100000)

Output

输出a的不同子序列的数量Mod 10^9 + 7。

Input示例

Output示例

13 //容易想到是 dp ，dp[i] 以 i 位置为结尾的子序列个数

1  # include 
        
          2 # include 
         
           3 # include 
          
            4 # include 
           
             5 # include 
            
              6 # include 
             
               7 # include 
              
                8 # include 
                9 # include 
                
                 10 # include 
                 
                  11 # include 
                  
                   12 # include 
                   
                    13 # include 
                    
                     14 # pragma comment(linker,"/STACK:102400000,102400000")15 using namespace std;16 #define MOD 100000000717 #define INF 0x3f3f3f3f18 #define LL long long19 #define MX 10000520 21 int n;22 int dat[MX];23 int zhi[MX];24 int pre[MX];25 LL sum[MX];26 LL dp[MX];27 28 int main()29 {30 scanf("%d",&n);31 for (int i=1;i<=n;i++)32 {33 scanf("%d",dat+i);34 pre[i] = zhi[dat[i]];35 zhi[dat[i]] = i;36 }37 for (int i=1;i<=n;i++)38 {39 if (pre[i]==0)40 dp[i] = (sum[i-1] + 1)%MOD;41 else42 dp[i] = (sum[i-1] - sum[pre[i]-1] + MOD)%MOD;43 sum[i] = (sum[i-1] + dp[i])%MOD;44 }45 printf("%lld\n",sum[n]);46 return 0;47 }

View Code

转载于:https://www.cnblogs.com/haoabcd2010/p/7668172.html

你可能感兴趣的文章