FZU 2129 子序列个数

2024-01-28 06:08
文章标签 序列 个数 fzu 2129

本文主要是介绍FZU 2129 子序列个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

        给一个序列,里面可能有相同元素,问能组成多少不同子序列。

        DP。一直想用dp(i)表示到序列a1~ai的答案,一直想不出来,其实有更好的做法。我们可以用dp(i)表示最后一个元素为ai的子序列有多少,sum(i)表示dp(1)~dp(i)的和。状态转移见代码。

#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <string.h>using namespace std;const int maxn = 1e6+10;
const int mod = 1e9+7;int n;
int a[maxn];
int lastpos[maxn];	//记录每个数最近出现的位置 
int dp[maxn];		//最后一个元素为ai的子序列个数 
int sum[maxn];		//前缀和 int main(){while(cin>>n){memset(lastpos,-1,sizeof(lastpos));memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){scanf("%d",&a[i]);}dp[1]=1;sum[1]=1;lastpos[a[1]]=1;for(int i=2;i<=n;i++){dp[i]=sum[i-1];dp[i]%=mod;if(lastpos[a[i]]!=-1){	//ai曾经出现过 dp[i]-= sum[lastpos[a[i]]-1];dp[i]+=mod;dp[i]%=mod;}else{					//ai未曾出现过,可以单独成为新的子序列 dp[i]++;}sum[i]=sum[i-1]+dp[i];sum[i]%=mod;lastpos[a[i]]=i;}cout<<sum[n]<<endl;}return 0;
}


这篇关于FZU 2129 子序列个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/652689

相关文章

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ

fzu 2277 Change 线段树

Problem 2277 Change Time Limit: 2000 mSec    Memory Limit : 262144 KB  Problem Description There is a rooted tree with n nodes, number from 1-n. Root’s number is 1.Each node has a value ai.