首页 > 代码库 > [BZOJ 3791] 作业 【DP】
[BZOJ 3791] 作业 【DP】
题目链接：BZOJ - 3791
题目分析
一个性质：将一个序列染色 k 次，每次染连续的一段，最多将序列染成 2k-1 段不同的颜色。
那么就可以 DP 了，f[i][j][0|1] 表示到第 i 个位置，染了 j 段，当前这一段颜色为 0|1 的最大价值。
f[i][][] 只与 f[i-1][][] 有关，第一维用滚动数组就可以了。
代码
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;const int MaxN = 100000 + 5, MaxM = 100 + 5;inline void Read(int &Num) { char c; c = getchar(); while (c < ‘0‘ || c > ‘9‘) c = getchar(); Num = c - ‘0‘; c = getchar(); while (c >= ‘0‘ && c <= ‘9‘) { Num = Num * 10 + c - ‘0‘; c = getchar(); }}inline int gmax(int a, int b) {return a > b ? a : b;}int n, m, Ans;int A[MaxN], f[3][MaxM][3];int main() { Read(n); Read(m); for (int i = 1; i <= n; ++i) Read(A[i]); int Now = 0, Last = 1; m = m * 2 - 1; Ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { f[Now][j][0] = gmax(f[Last][j][0], f[Last][j - 1][1]); f[Now][j][1] = gmax(f[Last][j][1], f[Last][j - 1][0]); if (A[i] == 0) ++f[Now][j][0]; else ++f[Now][j][1]; Ans = gmax(Ans, f[Now][j][0]); Ans = gmax(Ans, f[Now][j][1]); } Now ^= 1; Last ^= 1; } printf("%d\n", Ans); return 0;}
[BZOJ 3791] 作业 【DP】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。