2023-03-25 21:49 南开大学 Java 发布于河北
关注
招行信用卡笔试题
求助
输入整数a,整数b,01串str,可以修改str各个位的0和1，0变1或1变0，让字符串所有连续0的各个段长度都是a的倍数，所有连续的1各个段的长度都是b的倍数，输出最小修改次数。
如输入2,3,10111000，输出2，因为可以修改为11111100
输入整数a,整数b,01串str,可以修改str各个位的0和1，0变1或1变0，让字符串所有连续0的各个段长度都是a的倍数，所有连续的1各个段的长度都是b的倍数，输出最小修改次数。
如输入2,3,10111000，输出2，因为可以修改为11111100
全部评论
人才池是我家
美团_后端开发(准入职员工)
从后往前看，dp[n][0]表示以0结尾且前面都满足条件的最小代价，dp[n]可以由dp[n-ka]转移而来，但是其实dp[n-a]的计算也会包含前面的k，所以只需要dp[n][0]=max(dp[n-a][0]+dp[n-a][1])+diff(n-a,n)，diff表示区间内的非0数量，这个可以用前缀和维护，也就是把这段a长度都变为0,然后就像我上面说的dp[n-a][0]也会继续考虑前面a个0的情况所以这么转移没问题。接着就是dp[n][1]=max(dp[n-b][0],dp[n-b][1])+(b-diff(n-b,n))，不存在的地方存-1
瑞雪青年
北京大学 后端
m
摩力塔先辈
门头沟学院 后端
m
相关推荐
