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