cf868F. Yet Another Minimization Problem(决策单调性 分治dp)

题意

题目链接

给定一个长度为\(n\)的序列。你需要将它分为\(m\)段,每一段的代价为这一段内相同的数的对数,最小化代价总和。

\(n<=10^5,m<=20\)

Sol

看完题解之后的感受:

首先列出裸的dp方程,\(f[i][j]\)表示前\(i\)个位置,切了\(j\)次,转移的时候枚举上一次且在了哪儿

\(f[i][j] = max(f[k][j - 1] + w(k, i))\)

\(w(k, i)\)表示\([k, i]\)内相同的数的对数。。

然后sb的我以为拿个单调队列维护一下就完了结果发现转移是\(O(n)\)的??

标算真神仙Orz

因为转移不是\(O(n)\)的,所以我们可以分治的去做

假设当前要求的区间为\([l, r]\),可以从\([L, R]\)转移而来,\(mid = (l + r)/ 2\)的决策点为\(p\)

那么\([l, mid - 1]\)的转移区间一定在\([L, p]\),\([mid+1, r]\)的转移区间一定是\([p, R]\),递归的做即可

画出图来应该是这样的

求解区间:\(|\gets\)预处理\(\to |\) \(l\frac{\qquad\qquad\qquad\downarrow^{mid}\qquad\qquad\qquad}{}r\)

决策区间:\(L\frac{\qquad\qquad\qquad\downarrow^{p}\qquad\qquad\qquad}{}R\)

转移的时候需要记录每个数的出现次数,每次转移时\(O(1)\)的

总的时间复杂度为:\(O(nlognk)\)

推荐一篇写的不错的blog

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, K, a[MAXN], b[MAXN];
LL f[MAXN], g[MAXN];
void solve(int l, int r, int L, int R, LL w) {
    if(l > r) return ;
    int mid = l + r >> 1, p = min(mid, R), k = 0;
    for(int i = l; i <= mid; i++) w += b[a[i]]++;
    for(int i = L; i <= p; i++)   w -= --b[a[i]], f[mid] > g[i] + w ? f[mid] = g[i] + w, k = i : 0;

    for(int i = l; i <= mid; i++) w -= --b[a[i]];
    for(int i = L; i <= p; i++)   w += b[a[i]]++;
    solve(l, mid - 1, L, k, w);

    for(int i = L; i < k; i++)    w -= --b[a[i]];
    for(int i = l; i <= mid; i++) w += b[a[i]]++;
    solve(mid + 1, r, k, R, w);

    for(int i = l; i <= mid; i++) --b[a[i]];
    for(int i = L; i < k; i++)    ++b[a[i]];
}
main() {
    N = read(); K = read();
    for(int i = 1; i <= N; i++) a[i] = read(), g[i] = g[i - 1] + b[a[i]]++; memset(b, 0, sizeof(b));
    while(K--) {memset(f, 0x7f, sizeof(f)); solve(1, N, 1, N, 0); swap(f, g);}
    cout << f[N];
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

java面试小题系列(一)

963
来自专栏不止是前端

从实现一个Promise说起

1383
来自专栏mathor

线程同步

1313
来自专栏xingoo, 一个梦想做发明家的程序员

函数声明后面的const用法

void function() const{} 通常我们会看到一些函数声明后面会跟着一个const,这个const是做什么的呢? 看一下下面的例子,就知道了。直...

2095
来自专栏Dato

SQL 中的日期和时间类型

在我们SQL中一般支持三种数据类型。 date:日历日期,包括年(四位),月和日。 time: 一天中的时间,包括小时,分和秒。可以用变量time(p)来表示秒...

3356
来自专栏linux运维学习

linux学习第六十五篇:for循环,while循环, break跳出循环,continue结束本次循环

for循环 语法:for 变量名 in 条件; do …; done for循环会以空格作为分隔符 案例1 #!/bin/bash sum=0 for i ...

28710
来自专栏决胜机器学习

《Redis设计与实现》读书笔记(十) ——Redis对象相关其他设计与实现

《Redis设计与实现》读书笔记(十) ——Redis对象相关其他设计与实现 (原创内容,转载请注明来源,谢谢) 一、类型检查与命令多态 redis对键操作的命...

3006
来自专栏水击三千

JavaScript变量作用域

执行环境是JavaScript中比较重要的概念。执行环境定义了变量或者函数有权访问的其他数据决定了他们各自的行为,每个执行环境都有一个与之关联的变量,环境中定义...

2829
来自专栏程序员互动联盟

【编程基础第十一讲】代码如何写才最漂亮第一篇

存在问题: 好多小伙伴对编码的格式作用模糊,以为只要完成功能就行,其实这种观点是错误的,一定要重视代码规范,不然你哭的地都找不到。 如何实施: 良好的代码开发习...

2777
来自专栏九彩拼盘的叨叨叨

ES6 之 Proxy 介绍

Proxy(代理) 是 ES6 中新增的一个特性。Proxy 让我们能够以简洁易懂的方式控制外部对对象的访问。其功能非常类似于设计模式中的代理模式。

1063

扫码关注云+社区

领取腾讯云代金券