51nod 1202 子序列个数【计数DP】

╰半橙微兮° 2023-02-15 10:04 18阅读 0赞

子序列的定义：对于一个序列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的结果即可。

题目链接：http://www.51nod.com/Challenge/Problem.html\#problemId=1202  
题意：对于给定的序列，输出不同子序列的数量。  
思路：定义f\[i\]\[2\]表示前i个数的序列数量，其中0表示不选 1表示选。那么f\[i\]\[1\] = f\[i - 1\]\[0\] + f\[i - 1\]\[1\]  
f\[i\]\[0\]比f\[i\]\[1\]少了哪些情况呢，就是假设现在有两个相同的数位置分别为i，j，那么删除\[i, j-1\]与\[i+1, j\]  
形成的子序列是相同的，所以我们要减去这种情况

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod = 1e9 + 7;
    const int maxn = 1e6 + 10;
    ll f[maxn][2 ];
    int pos[maxn], a[maxn];
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        f[0][0] = 1;
        for(int i = 1; i <= n; ++i)
        {
            int d = pos[a[i]];
            pos[a[i]] = i;
            f[i][0] = f[i][1] = (f[i -   1][0] + f[i - 1][1]) % mod;
            if(d > 0) //减去重复计算的情况
                f[i][0] = ((f[i][0] - f[d - 1][0] - f[d - 1][1]) % mod + mod) % mod;
        }
        ll ans = f[n][0] + f[n][1];
        printf("%lld\n", (ans - 1) % mod);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关【计数DP】子序列个数

什么吊DP，根本不会 [题目-子序列个数 (51nod.com)][-_ _51nod.com] 题意： ![b111353c55234f59a30d1366d55a32

不念不忘少年蓝@/ 2024年03月22日 14:46/ 0 赞/ 118 阅读

相关 51nod 1134 最长递增子序列 dp(经典)

[1134 最长递增子序列][1134] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：基础题][Link 1] 收藏关注给出长度为N的数组

r囧r小猫/ 2024年02月17日 19:19/ 0 赞/ 35 阅读

相关 51nod 1202 子序列个数【计数DP】

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

╰半橙微兮°/ 2023年02月15日 10:04/ 0 赞/ 19 阅读

相关 51nod 1021石子归并 dp

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

Love The Way You Lie/ 2022年08月20日 13:11/ 0 赞/ 221 阅读

相关 51nod 1051 最大子矩阵和 dp

题意：一个M\N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。例如：3\3的矩阵： \-1 3 -1 2 -1 3

墨蓝/ 2022年08月20日 06:20/ 0 赞/ 218 阅读

相关 51nod1202 dp+递推

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

桃扇骨/ 2022年08月19日 14:28/ 0 赞/ 194 阅读

相关 51nod-1009-数位dp

题目链接：[51nod1009][] [1009 数字1的数量][51nod1009] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB

一时失言乱红尘/ 2022年07月15日 14:10/ 0 赞/ 215 阅读

相关 51 nod 1134 最长递增子序列

1134 最长递增子序列基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列

深碍√TFBOYSˉ_/ 2022年06月10日 12:20/ 0 赞/ 201 阅读

相关最长递增子序列 51Nod 1134 最长递增子序列

[1134 最长递增子序列][1134] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 0 [难度：基础题][Link 1] ![st

曾经终败给现在/ 2022年05月26日 00:52/ 0 赞/ 290 阅读

相关 51nod 1153 选择子序列

[51nod 选择子序列][51nod] 这道题是[\\(Bunny\\)][Bunny]学长在给我们的模拟赛中的一道题。食用单调栈，处理每个数\\(a\_i\\)左右第

桃扇骨/ 2021年10月26日 18:28/ 0 赞/ 294 阅读