01背包 + 思维
首先可以发现，开头是1的要分开要切一次，中间的切两次，末尾是1的切一次。
把切的次数看成花费，1的个数看成价值，就可以01背包求解了。
但是有一点要注意，中间的连续1的串如果放在末尾，其实有一个可以少切一次，所以我们不用花费那么多，比如切k次，我们的花费算出来是有的答案是k+1，这时候也只切了k次，所以我们直接把切的次数+1就可以了。
#include#define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)using namespace std;typedef long long ll;inline int lowbit(int x){ return x & (-x); }inline int read(){ int ret = 0, w = 0; char ch = 0; while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); } while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = getchar(); return w ? -ret : ret;}inline int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }inline int lcm(int a, int b){ return a / gcd(a, b) * b; }template inline T max(T x, T y, T z){ return max(max(x, y), z); }template inline T min(T x, T y, T z){ return min(min(x, y), z); }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 10005;int n, k, tot, c[N], w[N], dp[N];string s;void calc(const string &s){ for(int i = 0; i < s.size(); i ++){ if(s[i] == '1'){ ++ tot; while(s[i] == '1' && i < s.size()) i ++, w[tot] ++; } } if(s.front() == '1') c[1] = 1; if(s.back() == '1') c[tot] = 1; for(int i = 1; i <= tot; i ++){ if(!c[i]) c[i] = 2; }}int main(){ while(~scanf("%d%d", &n, &k)){ full(w, 0), full(c, 0), tot = 0; cin >> s; calc(s); if(k == 0){ if(s.front() == '1') printf("%d\n", w[1]); else printf("0\n"); continue; } full(dp, 0xcf); dp[0] = 0, k ++; for(int i = 1; i <= tot; i ++){ for(int j = k; j >= c[i]; j --){ dp[j] = max(dp[j], dp[j - c[i]] + w[i]); } } int ans = 0; for(int i = 0; i <= k; i ++) ans = max(ans, dp[i]); printf("%d\n", ans); } return 0;}