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 子序列个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---