请求添加dp标签
查看原帖
请求添加dp标签
709361
盐焗蛋楼主2023/12/29 21:37

可以将当前百合花的编号用数组 dd 保存,之后对 dd 进行dp即可。

#include <bits/stdc++.h>
using namespace std;
int n,k,cnt,d[105],dp[105];
char str[105];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>k;
	cin>>str+1;
	for(int i=1;i<=n;i++)
		if(str[i]=='1')
			d[++cnt]=i;
	for(int i=2;i<=cnt;i++){
		dp[i]=2e9;
		for(int j=i-1;j>=1;j--)
			if(d[i]-d[j]<=k){
				dp[i]=min(dp[i],dp[j]+1);
			}
			else break;
	}
	if(dp[cnt]!=2e9) cout<<dp[cnt];
	else cout<<-1;
}
2023/12/29 21:37
加载中...