51NOD 1202 子序列个数 DP

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1202&judgeId=225600

这题看起来挺复杂，但是真正的dp还是挺好理解的。唯独是想不到的，应该把样例模拟一遍。

比如1、2、4、2

考虑第一个，只有“1”这一个子序列

考虑前两个，有：“1”， “12”， “2”

前三个，有：“1”， “12”， “2”， “14”，“124”，“24”，“4”

可以发现，dp[i]是可以从dp[i - 1]推过来的，第一，打破dp[i - 1]的合法情况要保留，第二，可以加入字符a[i]和前i - 1个组成的不重复的情况结合，得到新的结果，第三，a[i]自己单独做一个。

所以如果不考虑重复，那么dp[i] = 2 * dp[i - 1] + 1

但是考虑前4个，则会出现重复的情况。

首先，dp[3]的应该全部照写下来。“1”， “12”， “2”， “14”，“124”，“24”，“4”

然后，用a[4]去结合的话。会有，"12"（重复）, "122", "22", "142", "1242", "242", "42", "2"（重复）

那么需要减去重复的部分，减去多少呢？

观察到，最近出现相同数字（那个数字2）的位置是2，而且dp[2] =3，哪么，就是用a[2]生成dp[2]的时候的合法情况和现在的重复了，因为用a[2]生成dp[2]的时候，也就是从dp[1]递推过来，我们也保存了dp[1]的合法情况，那么既然用dp[1] + a[2]生成了某些情况，那么当a[4] == a[2]的时候，就没必要再用dp[1]那些合法情况来生成dp[4]，因为已经保存在dp[2]中了。所以这个需要减去。

所以需要不断hash到最右的位置。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int MOD = 1e9 + ;

int a[ + ];

int tohash[ + ];

long long int dp[ + ];

void work () {

    int n;

    cin >> n;

    for (int i = ; i <= n; ++i) {

        cin >> a[i];

    }

    dp[] = ;

    tohash[a[]] = ;

    for (int i = ; i <= n; ++i) {

        if (tohash[a[i]]) {

            dp[i] = (dp[i - ] *  +  - (dp[tohash[a[i]] - ] + ) + MOD) % MOD;

        } else {

            dp[i] = (dp[i - ] *  + ) % MOD;

        }

        tohash[a[i]] = i;

    }

    printf("%d\n", dp[n]);

}

int main () {

    #ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work ();

    return ;

}

巴特西

51NOD 1202 子序列个数 DP

最新文章

热门文章