Gym - 101611B Byteland Trip DP

53 阅读 0 评论 35 点赞

我是靠谱客的博主粗犷白羊，最近开发中收集的这篇文章主要介绍Gym - 101611B Byteland Trip DP，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

给你一个序列，只包含>和<。

>代表这个点可以前往任何下标大于他的点，<代表这个点可以前往任何下标小于他的点。

对每个下标i，问有多少种方式使得经过每个点一次，最后结束在i处。

题解：

由于这个题又可以由左边，又可以由右边到达，所以普通的DP方式不行。

改变思路，设d1[i][j]代表前i个点时，有j个联通块，并且联通块都指向右的方案数。

d2[i][j]为i以及i以后的点有j个联通块的方案数。

那么对于点i，我们计算ans[i]时，只要枚举左右有几个联通块，然后左右相连计算方案数即可。

相当于先把左边和右边的方案分别计算，然后再合并。

d1[i][j] 可以这么转移，如果s[i]是 > ，那么i要么是一个联通块的结尾，要么是一个新的联通块，

如果s[i]是 < ，那么要么是一个联通块的起点，要么连接两个联通块。

代码：

#include <bits/stdc++.h>
#ifdef LOCAL
#define debug(x) cout<<#x<<" = "<<(x)<<endl;
#else
#define debug(x) 1;
#endif

#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#define lson id<<1,l,mid
#define rson id<<1|1,mid+1,r
#define lowbit(x) x&-x
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;
const double PI = acos (-1.);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e3 + 5;

char s[MAXN];

ll d1[MAXN][MAXN], d2[MAXN][MAXN];
ll fac[MAXN];


int main() {
#ifdef LOCAL
    freopen ("input.txt", "r", stdin);
#endif
    scanf ("%s", s + 1);
    int n = strlen (s + 1);
    d1[0][0] = 1;
    fac[0] = 1;
    if (n == 1) {
        puts("1");
        return 0;
    }
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (s[i] == '>') d1[i][j] = (d1[i - 1][j - 1] + d1[i - 1][j] * j) % MOD;
            else d1[i][j] = (d1[i - 1][j] * j % MOD + d1[i - 1][j + 1] * (j + 1) % MOD * j % MOD) % MOD;
        }
    }
    d2[n + 1][0] = 1;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= (n - i + 1); j++) {
            if (s[i] == '<') d2[i][j] = (d2[i + 1][j - 1] + d2[i + 1][j] * j) % MOD;
            else d2[i][j] = (d2[i + 1][j] * j % MOD + d2[i + 1][j + 1] * (j + 1) % MOD * j % MOD) % MOD;
        }
    }
    for (int i = 1; i <= n; i++) {
        ll ans = 0;
        for (int j = 0; j < i; j++) {
            ans += d1[i - 1][j] * d2[i + 1][j] % MOD * fac[j] % MOD * fac[j] % MOD * 2 % MOD;
            ans %= MOD;
            ans += d1[i - 1][j] * d2[i + 1][j + 1] % MOD * fac[j + 1] % MOD * fac[j] % MOD;
            ans %= MOD;
            ans += d1[i - 1][j + 1] * d2[i + 1][j] % MOD  * fac[j + 1] % MOD * fac[j] % MOD;
            ans %= MOD;
        }
        printf("%I64d ", ans);
    }
    return 0;
}