给定一个长度为N的字符串,只由0和1组成。但是某些位置上是“?”。这意味着我们可以在那里放置0或1。
现在的问题是,我们需要计算填充这些“?”位置的方法数,使得不能有K个0放在一起。
比如说,我们有长度为N=4的字符串,字符串为0??0。
假设K=3,则在这里我们只能在两个位置中的最多一个位置上放置“0”。因此,字符串为:
0100
0010
0110
所以答案是3。现在我们需要计算长度为N和K的给定字符串的制作方法数量。
我的方法是使用动态规划来解决这个问题,具有O(N,K)的时间复杂度。如果我们在第i个位置放置0,则可以在下一个连续的“?”段中放置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,字符串s=???L?R?LLL?L?L?L?LLL???L???RL?????LR?L?LLRL??R???L?RL????RL?R??LL??LLLR?R
答案应该是877905026。但是代码给出的是246470268。
?
数量的限制? - Pham Trung