algorithm - 计算没有 K 个连续零的字符串的方法

Question

给定一个长度为 N 的字符串，它只由 0 和 1 组成。但是字符串的某些位置是 '?'。这意味着我们可以放 0 或 1。

现在，问题是我们需要计算填充这些“?”的方法的数量。没有 K 个 0 可以放在一起的位置。

比如说我们有长度为 N=4 且字符串为 0??0 的字符串

然后让 K=3 然后在这里我们最多只能在两个位置中的一个位置放置“0”。所以字符串是:

0100
0010
0110

所以这里的答案是 3。现在对于给定的长度为 N 和 K 的字符串，我们需要计算生成该字符串的方法数。

我的方法:

现在我有 O(N,K) 的方法来解决这个问题，使用动态规划，如果我们把 0 放在第 i 个位置，我们可以在 '?' 的下一个连续段中放置 K-1 个零。如果我们放入 1，那么我们可以再次放入 K 个零。

但是N和K可以很大，那么他们有没有更好更高效的算法呢？

其中一个答案中提到的代码:

int n,k;
cin>>n>>k;
string s;
cin>>s;
s="#"+s;
int size=s.length();

vector<long long int>F(size+1);
F[0]=1;
for(int i=1;i<=size;i++){
    if(s[i]=='R')
    {
        F[i]=0;
    }       
    else if(s[i]=='L'){
        F[i]=1;
    }
    else{
        for(int j=i-1;j>=i-k;j--){
            if(j<0)
            break;
            F[i]=(F[i]+F[j])%MOD;
        }
    }
}
cout<<F[size]<<"\n";

现在它的测试用例有点大，但它失败了。但是我在强力解决方案上运行它，但它不匹配。

测试用例:n=73,k=7 and string s = ???L?R?LLL?L?L?L?LLL???L???RL?????LR?L? LLRL??R???L?RL????RL?R??LL??LLLR?R

答案应该是877905026，但代码给出的是246470268

Answer 1

提示

您可以使用数组 F[n] 来计算填充位置 [0,n) 的方式的数量，使得没有 K 个连续的 0，并且在位置 n-1 处有一个 1。

然后根据先前的结果计算 F[n+1]，我们知道在位置 n 处有一个 1，并且在 0 和 K-1 之间的前面有零。设零的个数为k。

F[0] = 1
F[n] = sum F[n-1-k] for k in 0,1,..,K-1 
   (only including values for k up to where the string at n-1-k is forced to be 1)

这应该给出正确答案，但需要时间 O(NK)。

但是，我们可以通过为 F[n] 的值维护一个前缀和来加速总和的计算。换句话说，如果我们存储数组 S[n]=F[0]+F[1]+F[2]+..+F[n]，我们可以通过减去 F 的特定索引来快速计算总和S[n]的两个值。

因此，通过跟踪强制 1 的最后位置，您可以计算 O(N) 中的递归。

最终答案将由F[N+1]给出。

示例 1

对于 K=3 和字符串 0??0 的示例:

F[0] = 1  (Just the empty string)
F[1] = 0 : position n-1=0 is forced to be 0 so no solutions are possible
F[2] = F[1]+F[0] = 1  (Just the string 01)
F[3] = F[2]+F[1]+F[0] = 2 (The strings 001 and 011)
F[4] = 0 : position n-1=3 is forced to be 0 so no solutions possible
F[5] = F[4]+F[3]+F[2] = 3  (the strings 0010 and 0110 and 0000)

所以最后的答案是3

示例 2

对于你的第二个例子 10???0??

F[0] = 1 (empty string)
F[1] = 1 (The string 1)
F[2] = 0
F[3] = F[2]+F[1] = 1 (The string 101)
F[4] = F[3]+F[2]+F[1] = 2 (The strings 1011 and 1001)
F[5] = F[4]+F[3]+F[2] = 3 (10011 and 10111 and 10001)
F[6] = 0
F[7] = F[6]+F[5]+F[4] = 5 (1011001, 1001001, 1001101, 1011101, 1000101)
F[8] = F[7]+F[6]+F[5] = 8 (10110011, 10010011, 10011011, 10111011, 10001011, 10011001, 10111001, and 10001001)
F[9] = F[8]+F[7]+F[6] = 13
           10110011, 10010011, 10011011, 10111011, 10001011, 10011001, 10111001, 10001001
           10110010, 10010010, 10011010, 10111010, 10001010

修复代码

您的代码几乎是正确的:将内部循环更改为如下所示，它会给出您想要的答案:

if(s[i]=='R')
{
    F[i]=0;
} else{
    for(int j=i-1;j>=i-k;j--){
        if(j<0)
            break;
        F[i]=(F[i]+F[j])%MOD;
        if (s[j]=='L')
            break;
    }
}