首先我们发现嘛。。。最多可以搞出2 *k - 1段不同的
于是一遍扫过去dp就可以啦，需要注意滚动数组
1 /************************************************************** 2 Problem: 3791 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:280 ms 7 Memory:1196 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 using namespace std; 15 const int N = 100005; 16 const int K =55; 17 18 int n, k, ans; 19 int a[N], f[2][K << 1][2]; 20 21 int main() { 22 int i, j, x, y, now; 23 scanf("%d%d", &n, &k); 24 for (i = 1; i <= n; ++i) 25 scanf("%d", a + i); 26 f[0][1][a[1]] = 1; 27 for (i = now = 1; i <= n - 1; ++i, now ^= 1) { 28 memset(f[now], 0, sizeof(f[now])); 29 for (j = 1; j <= k * 2 - 1; ++j) 30 for (x = 0; x <= 1; ++x) 31 for (y = 0; y <= 1; ++y) 32 f[now][j + (x != y)][y] = max(f[now][j + (x != y)][y], f[!now][j][x] + (a[i + 1] == y)); 33 for (j = 1; j <= k * 2 - 1; ++j) 34 ans = max(ans, max(f[now][j][0], f[now][j][1])); 35 } 36 printf("%d ", ans); 37 return 0; 38 }