Yet Another Minimization Problem
dp方程我们很容易能得出, f[ i ] = min(g[ j ] + w( j + 1, i ))。 然后感觉就根本不能优化。
然后就滚去学决策单调啦。 然后就是个裸题, 分治一下就好啦,
注意用分治找决策点需要的条件是我们找出被决策点不能作为当前转移的决策点使用。
如果w( j + 1, i )能很方便求出就能用单调栈维护, 并且找出的被决策点能当作当前转移的决策点使用。
我怎么感觉用bfs应该跑莫队的时候应该比dfs快啊, 但是居然还是dfs跑得快, 莫名其妙。。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n, k, a[N], cnt[N];
LL f[N], g[N]; int pl = , pr = ;
LL val; inline LL w(int i, int j) {
while(pl > i) pl--, val += cnt[a[pl]], cnt[a[pl]]++;
while(pr < j) pr++, val += cnt[a[pr]], cnt[a[pr]]++;
while(pl < i) cnt[a[pl]]--, val -= cnt[a[pl]], pl++;
while(pr > j) cnt[a[pr]]--, val -= cnt[a[pr]], pr--;
return val;
} void solve(int L, int R, int l, int r) {
if(l > r) return;
int mid = l + r >> , p = L;
for(int i = L; i <= min(R, mid); i++)
if(g[i] + w(i + , mid) < f[mid])
f[mid] = g[i] + w(i + , mid), p = i;
solve(L, p, l, mid - );
solve(p, R, mid + , r);
} int main() {
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
f[i] = f[i - ] + cnt[a[i]];
cnt[a[i]]++;
}
for(int i = ; i <= k; i++) {
memset(cnt, , sizeof(cnt));
memcpy(g, f, sizeof(g));
memset(f, INF, sizeof(f));
solve(, n, , n);
}
printf("%lld\n", f[n]);
return ;
} /*
*/
Codeforces 868F Yet Another Minimization Problem 决策单调性 (看题解)的更多相关文章
-
CodeForces 868F Yet Another Minimization Problem(决策单调性优化 + 分治)
题意 给定一个序列 \(\{a_1, a_2, \cdots, a_n\}\),要把它分成恰好 \(k\) 个连续子序列. 每个连续子序列的费用是其中相同元素的对数,求所有划分中的费用之和的最小值. ...
-
Codeforces 868F. Yet Another Minimization Problem【决策单调性优化DP】【分治】【莫队】
LINK 题目大意 给你一个序列分成k段 每一段的代价是满足\((a_i=a_j)\)的无序数对\((i,j)\)的个数 求最小的代价 思路 首先有一个暴力dp的思路是\(dp_{i,k}=min(d ...
-
Codeforces 868F Yet Another Minimization Problem(分治+莫队优化DP)
题目链接 Yet Another Minimization Problem 题意 给定一个序列,现在要把这个序列分成k个连续的连续子序列.求每个连续子序列价值和的最小值. 设$f[i][j]$为前 ...
-
Codeforces 868F. Yet Another Minimization Problem
Description 给出一个长度为 \(n\) 的序列,你需要将它分为 \(k\) 段,使得每一段的价值和最小,每一段的价值是这一段内相同的数的个数 题面 Solution 容易想到设 \(f[i ...
-
cf868F. Yet Another Minimization Problem(决策单调性 分治dp)
题意 题目链接 给定一个长度为\(n\)的序列.你需要将它分为\(m\)段,每一段的代价为这一段内相同的数的对数,最小化代价总和. \(n<=10^5,m<=20\) Sol 看完题解之后 ...
-
CF868 F. Yet Another Minimization Problem 决策单调优化 分治
目录 题目链接 题解 代码 题目链接 CF868F. Yet Another Minimization Problem 题解 \(f_{i,j}=\min\limits_{k=1}^{i}\{f_{k ...
-
【CodeForces】868F. Yet Another Minimization Problem
原题链接 题目大意是有N个数,分成K段,每一段的花费是这个数里相同的数的数对个数,要求花费最小 如果只是区间里相同数对个数的话,莫队就够了 而这里是!边单调性优化边莫队(只是类似莫队)!而移动的次数和 ...
-
Codeforces 258D Little Elephant and Broken Sorting (看题解) 概率dp
Little Elephant and Broken Sorting 怎么感觉这个状态好难想到啊.. dp[ i ][ j ]表示第 i 个数字比第 j 个数字大的概率.转移好像比较显然. #incl ...
-
Codeforces 865C Gotta Go Fast 二分 + 期望dp (看题解)
第一次看到这种骚东西, 期望还能二分的啊??? 因为存在重置的操作, 所以我们再dp的过程中有环存在. 为了消除环的影响, 我们二分dp[ 0 ][ 0 ]的值, 与通过dp得出的dp[ 0 ][ 0 ...
随机推荐
-
[综] Sparse Representation 稀疏表示 压缩感知
稀疏表示 分为 2个过程:1. 获得字典(训练优化字典:直接给出字典),其中字典学习又分为2个步骤:Sparse Coding和Dictionary Update:2. 用得到超完备字典后,对测试数据 ...
-
Linux 安装mysql+apache+php
安装mysql 1. yum install mysql mysql-server 2. 修改mysql密码 >use mysql >update user set passwor ...
-
JDBC中的PreparedStatement
PreparedStatement类从Statement中继承来. 可以将SQL语句传给数据库做编译处理,即在执行的SQL语句中包含一个或多个IN参数,可以设置IN参数值多次执行SQL语句,不必重新给 ...
-
用JS获取地址栏中的参数的简易方法
这个方法用起来超级简单,传入参数即可直接获取地址栏中的参数 代码如下 function GetQueryString(name) { var reg = new RegExp("(^|&am ...
-
使用Redis实现分布式锁
在天猫.京东.苏宁等等电商网站上有很多秒杀活动,例如在某一个时刻抢购一个原价1999现在秒杀价只要999的手机时,会迎来一个用户请求的高峰期,可能会有几十万几百万的并发量,来抢这个手机,在高并发的情形 ...
-
201521145048《Java程序设计》第14周学习总结
1. 本周学习总结 1.1 以你喜欢式(思维导图或其他)归纳总结多数据库相关内容. 1.数据库的定义:是为了实现一定目的按某种规则组织起来的"数据"的"集合". ...
-
HDU 4372 Count the Buildings [第一类斯特林数]
有n(<=2000)栋楼排成一排,高度恰好是1至n且两两不同.现在从左侧看能看到f栋,从右边看能看到b栋,问有多少种可能方案. T组数据, (T<=100000) 自己只想出了用DP搞 发 ...
-
MAC终端常用语法
这篇文章的重点不在于说是对终端语法的讲解,而是方便大家做语法备忘. 方便查找对应终端语法.所以使用了表格形式对常用终端语法进行了汇总, 但是并没有很多的讲解部分. 当然了这里记录的也都是十分基础的语法 ...
-
I/O系统(二)
程序查询流程1测试指令,查询IO设备是否就绪.2传送指令,当已经就绪时,执行传送功能.3转移指令,未就绪时,转移至继续测试IO设备的状态.当需要启动某一IO设备时,必须将该程序插入到现行程序中.1,由 ...
-
Vue的双向数据绑定
最简单的实现v-model数据绑定,只需要在一个组件里面有个props,加上一个value,然后当组件要去修改数据的时候, $emit一个input事件,并且把新的值传出去.这就实现了Vue里面的数据 ...