题目链接: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;
}

  

最新文章

  1. 做图表统计你需要掌握SQL Server 行转列和列转行
  2. CI框架源码阅读笔记5 基准测试 BenchMark.php
  3. C语言的结构体和C++结构体的区别
  4. mysql.msi安装流程
  5. 【转】在Windows下搭建React Native Android开发环境
  6. 【Leetcode】Binary Tree Level Order Traversal
  7. oracle1
  8. mma ctf 1st &amp;&amp; csaw 2015
  9. msm8916 dt选用规则
  10. go语言数据库操作, gorm框架
  11. MySQL初识
  12. Codeforces 888G(分治+trie)
  13. fetch请求
  14. Python编程--类的分析
  15. PL/SQL Developer从11.0.6版本开始32/64为之区分
  16. Week2 关于代码规范的一些认识
  17. Linux内核分析— —操作系统是如何工作的(20135213林涵锦)
  18. 【BZOJ】1798: [Ahoi2009]Seq 维护序列seq
  19. Windows Azure Storage (24) 启用Azure Blob日志
  20. Subarray Sum Equals K LT560

热门文章

  1. 分享一个很好看的WPF界面
  2. 使用WinINet和WinHTTP实现Http訪问
  3. java中获取系统属性以及环境变量
  4. web socket 心跳包的实现方案
  5. good page
  6. U盘安装centos 6.4教程(总算是弄好了
  7. rabbitmq 消息持久化
  8. gulp的常用api
  9. Deep Learning学习随记(二)Vectorized、PCA和Whitening
  10. 向RichTextBox控件不停的AppendText数据时,如何把光标的焦点始终显示到最后