链接：

题意：

考虑成，U位置的点要往后放，D位置往前放

Dp[i][j]表示处于i位置，还有j个U没有放下。

s[i] == 'D' : Dp[i][j] = Dp[i-1][j]j+Dp[i-1][j+1](j+1)

把d放到前面空出来j的位置中的一个，或者是j+1中的一个同时j+1中的一个U再放下来。

s[i] == 'U' : Dp[i][j] = Dp[i-1][j-1]+Dp[i-1][j]*j

拿起当前U或者，拿起的同时放一个U

代码：

// #include<bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<vector>

#include<string.h>

#include<set>

#include<queue>

#include<algorithm>

#include<math.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const int MOD = 1e9+7;

const int MAXN = 1e6+10;

int n, m, k;

char s[1010];

LL Dp[1010][1010];

int main()

{

    // freopen("test.in", "r", stdin);

    int t, cas = 0;

    scanf("%d", &t);

    while(t--)

    {

        printf("Case %d:", ++cas);

        scanf("%s", s);

        int len = strlen(s);

        Dp[0][0] = 1;

        for (int i = 1;i <= len;i++)

        {

            if (s[i-1] == 'U')

            {

                for (int j = 0;j <= len;j++)

                    Dp[i][j] = (Dp[i-1][j-1]+Dp[i-1][j]*j%MOD)%MOD;

            }

            else if (s[i-1] == 'D')

            {

                for (int j = 0;j < len;j++)

                    Dp[i][j] = (Dp[i-1][j]*j%MOD+Dp[i-1][j+1]*(j+1)%MOD*(j+1)%MOD)%MOD;

            }

            else

            {

                for (int j = 0;j <= len;j++)

                    Dp[i][j] = Dp[i-1][j];

            }

        }

        Dp[len][0] = (Dp[len][0]%MOD+MOD)%MOD;

        printf(" %lld\n", Dp[len][0]);

    }

    return 0;

}

巴特西

LightOJ - 1299 - Fantasy Cricket(DP，数学)

链接：

题意：

代码：

最新文章

热门文章

巴特西

LightOJ - 1299 - Fantasy Cricket(DP， 数学)

链接：

题意：

代码：

最新文章

热门文章

LightOJ - 1299 - Fantasy Cricket(DP，数学)