本题主要考察了dp

发布于 13 天前  0 次阅读


dp吗???

思维题,序列构造问题

代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n, m;

signed main() {
    cin >> n >> m;
    if (n <= 2) {
        cout << 0 << endl;//不构成长度为3的区间,没有坏区间
    } else if (n == m) {
        cout << n - 2 << endl;//字符串全部由1构成,坏区间为n-2个
    } else if (m == 0) {
        cout << 0 << endl;//字符串全部由0构成,没有坏区间
    } else {
        int ls = n - m;//0的个数
        while (ls >= 2 && m > 0) ls -= 2, m--;//尽可能的把0分配给区间,每个好区间至少有2个0,和1个1
        cout << max(0, m - 1) << endl;//如果还有1,那么就是坏区间
    }
    return 0;
}