【计数DP】子序列个数

不念不忘少年蓝@ 2024-03-22 14:46 40阅读 0赞

**什么吊DP，根本不会**

[题目-子序列个数 (51nod.com)][-_ _51nod.com]

题意：

![b111353c55234f59a30d1366d55a32d8.png][]

思路：

ai在1e6之内，因此ai可以放在数组中

![1be879a0d51247be89f7c2e1ebca6bb9.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    
    int N;
    int a[mxn],dp[mxn],pos[mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N;i++){
    		if(pos[a[i]]==0) dp[i]=(2*dp[i-1]+1)%mod;
    		else{
    			dp[i]=((2*dp[i-1]-dp[pos[a[i]]-1])%mod+mod)%mod;
    		}
    		pos[a[i]]=i;
    	}
    	cout<<dp[N]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[-_ _51nod.com]: http://www.51nod.com/Challenge/Problem.html#problemId=1202
[b111353c55234f59a30d1366d55a32d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/126554d21eb843bb94142f3aae17b0c9.png
[1be879a0d51247be89f7c2e1ebca6bb9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/cbd9338c7b2749d6bdcb1d515be19874.png

发表评论取消回复

表情：

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

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

相关阅读

相关【子序列DP】CF1582 F1

[Problem - F1 - Codeforces][] 题意： ![3c5382553d7a4b58aca13a69ceb6e942.png][] 思路：很经典的

待我称王封你为后i/ 2024年03月23日 18:43/ 0 赞/ 33 阅读

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

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

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

相关【枚举区间思想+DP】子串的子序列

[F-子串的子序列\_牛客小白月赛62 (nowcoder.com)][F-_62 _nowcoder.com] 题意： ![45d4a87408594a30ac7cc22

港控/mmm°/ 2024年03月16日 20:02/ 0 赞/ 10 阅读

相关最长递增子序列的个数

最长递增子序列的个数 package com.bingoabin.algorithm.dp; / @Author: xubin34 @Date:

我不是女神ヾ/ 2022年09月12日 03:57/ 0 赞/ 154 阅读

相关简单dp 最大连续子序列

//设n个元素的序列存储在数组A[1...n]中，求数组中连续子序列之和的最大值。 include <iostream> include <c

妖狐艹你老母/ 2022年08月18日 01:00/ 0 赞/ 159 阅读

相关计数（dp

描述：计算从1到n中，每个数字（0到9）出现的次数其中sum[j]和dp[i]表示：数字i中 j 的个数；比如sum[1]和dp[5]就可以表示：5中1的

梦里梦外;/ 2022年06月18日 00:29/ 0 赞/ 169 阅读

相关 CodeForces - 255C——dp子序列

Think: 1题意描述：输入一个序列，寻找一个隔位相等的最长子序列 2状态转移方程： dp\[i\]\[j\] = dp\[j\]\[k\] + 1(a\[j\]

ゝ一纸荒年。/ 2022年06月13日 00:59/ 0 赞/ 117 阅读

相关最长公共子序列(DP)

给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这两个字符串

た入场券/ 2022年06月10日 11:41/ 0 赞/ 129 阅读

相关最长上升子序列（DP）

问题描述一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列

落日映苍穹つ/ 2022年06月10日 10:36/ 0 赞/ 241 阅读

相关被3整除的子序列DP

链接：[https://ac.nowcoder.com/acm/problem/21302][https_ac.nowcoder.com_acm_problem_21302]

我不是女神ヾ/ 2021年11月16日 23:28/ 0 赞/ 220 阅读