51nod1202 dp+递推

桃扇骨 2022-08-19 14:28 159阅读 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的结果即可。

分析：

我们定义dp\[i\]为以第i个数字结尾的子序列的个数。

这样我们可以看到，当第i个数字是在这组数中第一次出现的时候，不会出现重复的情况，所以这时候dp\[i\]就等于dp\[1\]+dp\[2\]+.....+dp\[i-1\]+1,最后再加上1的原因是单独的一个数字的情况。

但是假设这个数字不是第一次出现的，即在前i-1个数中已经出现过这个数字了，那么就会出现很多重复的情况，这是我们只需要找到离他最近的那个相同的数字出现的位置就可以了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    #define mod 1000000007
    #define LL long long
    
    int const maxn = 100005 ;
    
    int a[maxn];
    int b[maxn];
    int c[maxn];
    LL dp[maxn];
    LL sum[maxn];
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            memset(c,0,sizeof(c));
            memset(dp,0,sizeof(dp));
            memset(sum,0,sizeof(sum));
            for(int i = 1 ; i <= n ; i++)
            {
                scanf("%d",&a[i]);
                if(b[a[i]]!=0)c[i] = b[a[i]] ;
                else c[i] = i ;
                b[a[i]] = i ;
            }
            dp[1]=1;sum[1]=1;
            for(int i = 2 ; i <= n ; i++)
            {
                if(c[i]==i)dp[i]=(sum[i-1]+1)%mod;
                else dp[i] = (sum[i-1] - sum[c[i]-1]+mod)%mod;
                sum[i] = (sum[i-1]+dp[i])%mod;
            }
    //        for(int i = 1 ; i <= n ; i++)
    //        {
    //            cout<<dp[i]<<endl;
    //        }
            printf("%I64d\n",sum[n]);
        }
        return 0;
    }