【挑战题】01串 P1247

思路

可以用f[i]表示能否走到位置i，1表示能，0表示不能。状态转移时，需要找到能跳到i的位置，并检查其中是否存在1。由于检查的是连续的一段，因此可以用前缀和来优化。sum[x]表示f数组以x结尾的前缀和。借助前缀和可以快速检查l到r的一段f值是否均为0。最终输出答案f[n]即可。

完整代码

#include <bits/stdc++.h>
using namespace std;
int a,b,n;;
string s;
int f[100005],sum[100005];
int main(){
    cin>>s;
    cin>>a>>b;
    n=s.size();
    s="@"+s;//为了方便
    f[1]=sum[1]=1;
    for (int i=2;i<=n;i++) {
	    if (s[i]=='0') {
		    int l=max(1,i-b),r=i-a;
		    if (l<=r&&sum[r]-sum[l-1]>0) {
			    f[i]=1;
		    }
	    }
	    sum[i]=sum[i-1]+f[i];
    }
    cout<<f[n]<<endl;
    return 0;
}

点赞点赞😄

可以用f[i]表示能否走到位置i，1表示能，0表示不能。

状态转移时，需要找到能跳到i的位置，并检查其中是否存在1。

由于检查的是连续的一段，因此可以用前缀和来优化。sum[x]表示f数组以x结尾的前缀和。借助前缀和可以快速检查l到r的一段f值是否均为0。

最终输出答案f[n]即可。

n = s.size();
s = "#" + s;
f[1] = sum[1] = 1;
for (int i = 2; i <= n; i++) {
	if (s[i] == '0') {
		int l = max(1, i - b), r = i - a;
		if (l <= r && sum[r] - sum[l - 1] > 0) {
			f[i] = 1;
		}
	}
	sum[i] = sum[i - 1] + f[i];
}
cout << f[n] << endl;