当前位置: 首页 > news >正文

CF868F题解

先考虑朴素的暴力,设 \(f_{k,i}\) 表示前 \(i\) 个数划分为 \(k\) 段的最小代价,有 \(f_{k,i}=\min_j\{f_{k-1,j-1}+w(j,i)\}\) ,其中, \(w(x,y)\) 表示 \([x,y]\) 中相同元素的对数。

可以先在外层枚举 \(k\) ,考虑如何处理 \(f_i\) 的转移。记数组 \(g\) 为枚举上一个 \(k\) 时的 \(f\) 。假设有转移决策点 \(u\)\(v,u<v\) ,假设 \(i\)\(v\) 转移,则有\(g_v+w(v+1,i)<g_u+w(u+1,i)\) ,由于区间 \([u+1,i]\) 中的数的种类不少于区间 \([v+1,i]\) ,所以\(w(u+1,i+1) \geq w(v+1,i+1)\) ,即 \(g_v+w(v+1,i+1)<g_u+w(u+1,i+1)\) ,也就是说,对于大于 \(i\) 的点,都不会从 \(u\) 转移,即 \(f_i\) 具有决策单调性。

考虑整体二分。待转移区间 \([l,r]\) ,和决策点区间 \([fl,fr]\) ,对于 \([l,r]\) 的中点 \(mid\) ,暴力的找出其对应的决策点 \(pos\) ,然后递归处理即可。

如何计算 \(w(x,y)\) ,可以使用类似莫队的东西去维护,均摊下来复杂度是 \(O(1)\) 的。

总的复杂度就是 \(O(kn\log n)\) 的。

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,a[100005],f[100005],g[100005],cnt[100005],ml,mr,w;
inline void add(ll x){if(x)w+=cnt[a[x]],cnt[a[x]]++;}
inline void del(ll x){if(x)cnt[a[x]]--,w-=cnt[a[x]];}
inline void move(ll l,ll r){while(mr<r)add(++mr);while(ml>l)add(--ml);while(mr>r)del(mr--);while(ml<l)del(ml++);
}
void solve(ll l,ll r,ll fl,ll fr){if(fl==fr){	for(ll i=l;i<=r;i++){move(fl,i);f[i]=g[fl-1]+w;}return ;}ll mid=(l+r)>>1,pos,minn=1e16;for(ll i=fl;i<=min(fr,mid);i++){move(i,mid);ll v=g[i-1]+w;if(v<=minn)minn=v,pos=i;}f[mid]=minn;if(l==r)return ;solve(l,mid,fl,pos);solve(mid+1,r,pos,fr);
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;for(ll i=1;i<=n;i++){cin>>a[i];g[i]=g[i-1]+cnt[a[i]];cnt[a[i]]++;}memset(cnt,0,sizeof(cnt));w=0;for(ll i=2;i<=k;i++){solve(1,n,1,n);for(ll j=1;j<=n;j++)g[j]=f[j];}cout<<g[n];return 0;
}
http://www.hskmm.com/?act=detail&tid=21102

相关文章:

  • ThinkPHP反序列化分析
  • AT_iroha2019_day4_l 题解
  • AT_abc290_f 题解
  • 一张图读懂绿电直连系统架构 - 智慧园区
  • P5469 [NOI2019] 机器人 题解
  • 题解:P14080 [GESP202509 八级] 最小生成树
  • 实用指南:Spring Cloud Gateway 实战:全局过滤器日志统计与 Prometheus + Grafana 接口耗时监控
  • GTSAM 中自定义因子(Custom Factor)的详解和实战示例 - 指南
  • AtCoder AGC073 A 题解
  • CF506C Mr. Kitayuta vs. Bamboos 51nod1457 小K vs. 竹子 题目分析
  • 北京 意大利 硕士学签/D签 vfs代办 材料清单
  • temp
  • 我有园子了
  • 使用 Jenkins 的流水线方案实施 CI/CD
  • 加密的病例单
  • 详细介绍:视频融合平台EasyCVR构筑智慧交通可视化管理与智能决策中枢
  • docker 在x86上build arm 镜像
  • 9.29软工
  • 不一样的.NET烟火,基于Roslyn的开源代码生成器
  • 复刻江协旋钮控制模块
  • 告别硬编码!5个让Web自动化脚本更稳定的定位策略
  • 从零开始,使用Idea工具搭建一个springboot项目
  • 最优/极值问题的算法选择
  • 第三方控件库的添加和使用
  • C4NR PVP服务器1.2 天穹炮塔更新
  • 树形dp [JOI Open 2020] 发电站 / Power Plant
  • 深入解析:灵画-AI绘画小程序
  • AT_arc156_b [ARC156B] Mex on Blackboard
  • 产品排序
  • 环形链表II-leetcode