Algoogle

Algorithm for Programming Contest

Typical DP Contest O - 文字列

Category: TDPC Tag: dp

O - 文字列

問題概要


解法


基本的に文字の間をみていく.その両側が同じ文字ならダメ.違う文字ならok.

dp[i][j] := i番目のアルファベットまでやって同じ文字が隣り合う場所がj箇所あるときの場合の数

0個の文字はいらないので取り除く
i番目までの総文字数をsum[i+1]とする

i番目のアルファベットでダメな場所がj個のときいい場所はsum[i]+1-j個.
次にそのときのdpの更新.
freq[i]個の文字を何分割かしていい場所とダメな場所に入れていくことを考える.
分割数をkとして,ダメな場所にl個入れるとき,いい場所に入れる個数はk-l個.
この操作をしたとき,次のダメな場所の個数はj-l+freq[i]-k.あとは入れる場所の組合せを掛けあわせれば良い.
つまり,

をdp[i+1][j-l+freq[i]-k]に加える.

コード


(O.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

const int mod = 1e9+7;
inline void add(int &x, int y) { x=(x+y)%mod; }
inline int mul(int x, int y) { return 1LL*x*y%mod; }

int n, f[32], dp[32][310], c[310][310], sum[32];

int solve()
{
    rep(i,300) {
        c[i][0] = 1;
        repi(j,1,i+1) c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
    }

    sort(f,f+26);
    n = 26-(upper_bound(f,f+26,0)-f);
    reverse(f,f+26);

    rep(i,n) sum[i+1] = sum[i]+f[i];
    dp[0][0] = 1;
    rep(i,n) rep(j,sum[i]+1) repi(k,1,f[i]+1) rep(l,min(j,k)+1)
        add(dp[i+1][j-l+f[i]-k], mul(dp[i][j], mul(c[f[i]-1][k-1], mul(c[j][l], c[sum[i]+1-j][k-l]))));
    return dp[n][0];
}

void input()
{
    rep(i,26) cin >> f[i];
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    input();
    cout << solve() << endl;
    return 0;
}

Comments