51Nod 1202 子序列个数(动态规划)

Dynamic Programming

Posted by Scalpel on June 3, 2016

题目链接

题意:

子序列的定义:对于一个序列。则非空序列为a的一个子序列,其中。 例如4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。对于给出序列a,有些子序列可能是相同的,这里只算做1个,请输出a的不同子序列的数量。由于答案比较大,输出的结果即可。

思路:

  参考资料
  假设子序列的前k个数的子序列个数为,那么前k-1个子序列的个数就为个子序列,从k-1到k的变化是怎样的呢?
  1、假设数组a[N]第k个数为a[k],如果a[k] 与前面的k-1个数都不相同,那么就有: 为什么呢?可以这样想,对于前k-1项的子序列个数为,那前k个数,无非就是在前k-1项的基础上多加了一个数a[k](a[k]与前k-1个数任意一个都不相等),那就在原来的组合上加上a[k],子序列个数就多了个,还有一个a[k]自己构成一个子序列,所以还要加1;
  2、假设a[k]与前面的k-1个数其中一个相等,那依旧加上前k-1个子序列个数,但是由于前面有与a[k]相等的数,所以要减掉重复的部分,如何找到重复的部分呢,假设离k最近的一个与a[k]相等的数为第t个,即序列;我们已经知道序列的序列个数为,那么就是重复的部分,这里需要自己做好思考,也是算法的关键部分,这里我要解释的地方是,为什么只需要找到离k最近的t使得?给出的解释是:我们是从对数组进行遍历的,计算的i就是从1到n依次计算的,那么第一次遇到的情况满足条件:有且仅有一个t使得,比如序列,分别计算;我们在计算的时候发现(假设下标从1开始),所以;当计算的时候也有,但是由于我们前面已经把a[2]重复的部分减掉了,所以不需要再减,.
  状态转移方程为:
   
    从k往前存在离k最近的t,使得.
  设数组ap记录每个数字最近出现的位置,利用上面的方程即可求解,注意在第二个方程要加上MOD再求余,因为有可能出现负数。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;

#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);
const int INF = 0x3f3f3f3f;
const int N = 100001;
const int MOD = 1e9 + 7;

int a[N], ap[N];
long long dp[N];
int main()
{
#ifndef ONLINE_JUDGE
    FILEREAD
#endif
    FIO 
    int n;
    cin >> n;
    for (int i{1}; i <= n; ++i)
        cin >> a[i];
    for (int i{1}; i <= n; ++i)
    {
        if (ap[a[i]] == 0)
        {
            dp[i] = (dp[i - 1] * 2 + 1) % MOD;
            ap[a[i]] = i;
        }
        else
        {
            dp[i] = (dp[i - 1] * 2 - dp[ap[a[i]] - 1] + MOD) % MOD;
            ap[a[i]] = i;
        }
    }
    cout << dp[n] << endl;
    return 0;
}