1

これは、この問題に関連しています。f(n , k) を計算する必要があります。これは、1 の最長部分文字列の長さが k である長さ n のバイナリ文字列の数です。再帰を考えるのに苦労しています。

i 桁目が 0 の場合は、対応できると思います。具体的には、i 番目の数字が 1 であると考えると、解をサブ問題 f(i-1 , j) に拡張することができません。

少しわかりにくい場合は申し訳ありません。どんな指針も大いに役立つでしょう。ありがとう。

4

3 に答える 3

1

s を長さkパターンの開始インデックスとします。次に、s は次のとおりです。1 から nk まで。

各 s について、Sting S を 3 つの文字列に分割します。

PRE(s,k,n) = S[1:s-1] 
POST(s,k,n)=S[s+k-1:n] 
ONE(s,k,n) which has all 1s from S[s] to S[s+k-1]

PRE および POST の 1 の最長部分文字列は k 未満である必要があります。

させて

x = s-1 
y = n-(s+k)-1

NS(p,k) を、k 以上のサイズの最長部分文字列を持つ方法の総数とします。

NS(p,k) = sum{f(p,k), f(p,k+1),... f(p,p)}

終了条件:

NS(p,k) = 1 if p==k, 0 if k>p
f(n,k) = 1 if n==k, 0, if k > n.

長さ n の文字列の場合、1 の最長部分文字列が k = 2^n - NS(n,k) より小さいサイズになるような順列の数。

f(n,k) = Sum over all s=1 to n-k 
         {2^x - NS(x,k)}*{2^y - NS(y,k)}

つまり、最長部分文字列がサイズ k 未満である前後の部分文字列のそれぞれの順列の数の積です。

したがって、繰り返し発生するサブ問題と、DP できる再利用がたくさんあります。

後で追加: 以下のコメントに基づいて、NS に入る必要はないと思います。S(p,k) を次のように定義できます。

S(p,k) = sum{f(p,1), f(p,2),... f(p,k-1)}

と

f(n,k) = Sum over all s=1 to n-k 
         S(x,k)*S(y,k)
于 2012-07-15T05:53:20.840 に答える
1

状態空間を拡張すれば、動的計画法のバリエーションを使用してテーブルを構築できると思います。長さ n の異なるバイナリ文字列の数として定義される f(n,k,e) を計算するとします。これは、長さ 1 の最長部分文字列が高々 k で、行の e 1 で終わるものです。与えられた n に関連付けられた k と e のすべての可能な値について f(n,k,e) を計算した場合、e で分割された値があるため、f(n+1,k,e) を計算できます。 ) k と e のすべての可能な値 - n の長さの文字列を 0 または 1 で拡張したときに何が起こるかは、その時点でいくつの 1 で終わるかによって異なります。

于 2012-07-15T04:29:25.160 に答える
0

誰かが望むなら、これはかなり古い質問だと思います。私の小さな答えを明確にすることができます..

これが私のコードです

#include<bits/stdc++.h>
using namespace std;
long long DP[64][64];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int i,j,k;
    DP[1][0]=1;
    DP[1][1]=1;
    DP[0][0]=1;
    cout<<"1 1\n";
    for(i=2;i<=63;i++,cout<<"\n")
        {
            DP[i][0]=1;
            DP[i][i]=1;
            cout<<"1 ";
            for(j=1;j<i;j++)
            {
                for(k=0;k<=j;k++)
                    DP[i][j]+=DP[i-k-1][j]+DP[i-j-1][k];
                DP[i][j]-=DP[i-j-1][j];
                cout<<DP[i][j]<<" ";
            }
            cout<<"1 ";
        }
    return 0;
}

DP[i][j] は F(i,j) を表します。

移行/再発 (考えにくい):

F(i,j) を考慮すると、次のようになります。

1) k 個の 1 を右側に配置し、0 を使用してそれらを区切ることができます。つまり、文字列 + 0 + k 回 '1' です。F(ik-1,j) 注 : k=0 は、右側に 0 だけを保持していることを意味します!

2) 右の j+1 位置が 0 と j '1' で満たされ、すべての左が長さ j の連続した文字列を形成しない方法を見逃しています!! F(ij-1,k) (コードで k を使用したという理由だけで両方を示すために k を使用したことに注意してください。他の変数も定義できます!)

于 2015-07-17T19:22:18.850 に答える