题解 | #K 本题主要考察了dp #2023牛客寒假算法基础集训营1
本题主要考察了dp
https://ac.nowcoder.com/acm/contest/46800/K
K 本题主要考察了dp
不过本人没用dp，总结了规律写的
其实思考后可以想出当字符是100100100100...这样时坏区间总数最少，只要考虑最后那段就行，因为前面不存在坏区间
只要考虑字符串最后的情况就行
...100100
...100101
...100111
...101111
大概就这么几种，会发现从某一位置后都是坏区间，只要找准那个位置就可以了
当然切记不要忘了考虑n==m的情况！！！
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
if(n==m){
cout<<n-2;
}else if((n-1)/3+1>=m){
cout<<0;
}else{
cout<<m-((n-m)/2+1);
}
}
class HelloWorld {
public static void main(String[] args) {
System.out.println("还没写，反正也差不多");
}
}
编程比赛题解 文章被收录于专栏
各类编程比赛题解
腾讯泡池子531人在聊