C. Mahmoud and a Message dp + 暴力

http://codeforces.com/contest/766/problem/C

关键在于dp，如何计数。

设dp[i]表示前i个字母中，能分成多少份合法的情况。那么答案就是dp[n]，其中dp[0] = 1;

比如说：aab的，也就是样例。

对于每一个i，枚举其往后能组合成那个，比如b，能组合成b，也就是自己一个，或者ab，但是不能aab，因为违反了条件。

那么，组合成b的时候，就应该加上dp[2]的值，也就是前2个分成的合法情况有多少种，b作为单独一个插去后面。

ab同理。

dp[1] = 1，也就是只有a，

dp[2] = 2，有a/a 和 aa

dp[3] = 3，有a/a/b、aa/b和a/ab

#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 + ;

const int maxn = 1e3 + ;

int cnt[maxn][ + ];

char str[maxn];

int a[maxn];

int dp[maxn];

bool check(int last, int pre) {

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

        if (cnt[last][i] - cnt[pre - ][i] !=  && last - pre +  > a[i]) return false;

    }

    return true;

}

void work() {

    int n;

    cin >> n;

    cin >> str + ;

    for (int i = ; i <= ; ++i) cin >> a[i];

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

        for (int j = ; j <= ; ++j) {

            if (str[i] - 'a' +  == j) {

                cnt[i][j] = cnt[i - ][j] + ;

            } else cnt[i][j] = cnt[i - ][j];

        }

    }

    int ansone = , anstwo = -inf;

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

        for (int j = i; j >= ; --j) {

            if (check(i, j)) {

                anstwo = max(anstwo, i - j + );

            } else break;

        }

    }

    int ansthree = ;

    int pre = ;

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

        if (check(i, pre) == false) {

            ansthree++;

            pre = i;

        }

    }

    dp[] = ;

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

        for (int j = i; j >= ; --j) {

            if (!check(i, j)) break;

            dp[i] += dp[j - ];

            dp[i] %= MOD;

        }

    }

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

//        cout << dp[i] << endl;

//        ansone += dp[i];

//        ansone %= MOD;

//    }

//    ansone = (ansone + MOD - n + 1) % MOD;

    cout << dp[n] << endl;

    cout << anstwo << endl;

    cout << ansthree << endl;

}

int main() {

#ifdef local

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

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

#endif

    IOS;

    work();

    return ;

}

巴特西

C. Mahmoud and a Message dp + 暴力

最新文章

热门文章