hdu6376 度度熊剪纸条

思路：
01背包。有些细节需要注意一下，比如k = 0的情况。
实现：
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int, int> pii;
 4 const int INF = 0x3f3f3f3f;
 5 
 6 int dp[10005];
 7 
 8 int main()
 9 {
10     int n, k; string s;
11     while (cin >> n >> k >> s)
12     {
13         k++;
14         fill(dp, dp + k + 1, -INF);
15         vector<pii> v;
16         int begin = 0;
17         for (int i = 0; i < n; i++)
18         {
19             int j = i;
20             while (j < n && s[j] == '1') j++;
21             if (j - i)
22             {
23                 if (i == 0) { v.push_back(pii(1, j - i)); begin = j - i; }
24                 else if (j == n) v.push_back(pii(1, j - i));
25                 else v.push_back(pii(2, j - i));
26                 i = j;
27             }
28         }
29         if (k == 1) { cout << begin << endl; continue; }
30         dp[0] = 0;
31         for (int i = 0; i < v.size(); i++)
32         {
33             for (int j = k; j >= 0; j--)
34                 if (j >= v[i].first)
35                     dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second);
36         }
37         int ans = 0;
38         for (int i = 0; i <= k; i++) ans = max(ans, dp[i]);
39         cout << ans << endl;
40     }
41     return 0;
42 }