1

这是参考这个问题。我们需要计算 f(n , k)，它是长度为 n 的二进制字符串的数量，其中最长的子串的长度为 k。我在提出递归时遇到了麻烦。

第 i 个数字是 0 的情况，我想我可以处理。具体来说，当我认为第 i 个数字是 1 时，我无法将解决方案扩展到子问题 f(i-1 , j) 。我如何将两者拼接在一起？

对不起，如果我有点不清楚。任何指针都会有很大帮助。谢谢。

4

3 回答 3

1

如果您扩展状态空间，我认为您可以使用动态编程的变体来构建表格。假设您计算 f(n,k,e) 定义为长度为 n 的不同二进制字符串的数量，其中最长为 1s 的子串最多为 k 并且以 e 连续 1s 结尾。如果您已经计算了与给定 n 关联的 k 和 e 的所有可能值的 f(n,k,e)，那么，因为您将这些值除以 e，您可以计算 f(n+1,k,e ) 对于 k 和 e 的所有可能值 - 当你用 0 或 1 扩展一个 n 长字符串时，它会发生什么取决于它现在以多少个 1 结尾，你知道这是因为 e。

于 2012-07-15T04:29:25.160 回答
1

设 s 为长度为k的模式的起始索引。那么 s 在：1 到 nk。

对于每个 s，我们将 Sting S 分成三个字符串：

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 的字符串，1s 的最长子串的大小小于 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的每个前子串和后子串的排列数的乘积。

所以我们有一个重复的子问题，以及一大堆可以 DPed 的重用

稍后补充： 根据下面的评论，我想我们真的不需要进入 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 回答
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 1s 放在右边，并使用 0 即 String + 0 + k times '1' 将它们分开。F(ik-1,j) 注意：k=0 表示我只在右边保留 0！

2）我错过了右侧 j+1 位置填充 0 和 j '1' 的方式，并且所有左侧都没有形成任何长度为 j 的连续字符串！F(ij-1,k) （注意我使用 k 来表示两者只是因为我在我的代码中这样做了，你也可以定义其他变量！）

于 2015-07-17T19:22:18.850 回答