首页 > 其他分享 >题解 Yet Another Minimization Problem

题解 Yet Another Minimization Problem

时间:2023-07-17 21:33:50浏览次数:52  
标签:cnt Minimization val 题解 ll Delta rm Problem operatorname

Yet Another Minimization Problem

神仙题。

第一眼看上去就是 DP。

定义 \(f_{i,j}\) 表示当前点 \(i\),分 \(j\) 段的最小费用。

\(f_{i,j}= \min(f_{i,j},f_{k,j-1}+val_{k+1,i})\)

然后发现复杂度 \(O(n^2k)\),直接 T 飞,需要优化。

我们发现 \(j\) 那一维可以滚掉,也就是只考虑第一维,然后做 \(j\) 次就行了,下面称 \(f_{i,j}\) 为 \(f_i\)。

对于 \(val_{i,j}\),我们发现当 \(j\) 固定时,\(i\) 越小,值越大 (废话。

接下来最关键的一步就是证明转移的最优决策点是单调不降的。

我们考虑反证法。

定义 \(u\) 为当前点 \(i\) 的最优决策点,\(v\) 为 \(i+1\) 的最优决策点。

那么 \(f_u+\operatorname{val}(u+1,i) \le f_v+\operatorname{val}(v+1,i)\)

若 \(v < u\),则对于 \(i+1\) 应当满足:\(f_v+\operatorname{val}(v+1,i+1) \le f_u+\operatorname{val}(u+1,i+1)\)

即:\(f_v+\operatorname{val}(v+1,i)+ \Delta v \le f_u+\operatorname{val}(u+1,i)+ \Delta u\)

根据之前发现的单调性,显然可以得出 \(\Delta v \ge \Delta u\),即 \(\Delta v-\Delta u \ge 0\)。

所以移项可得 \(f_u+\operatorname{val}(u+1,i) \ge f_v+\operatorname{val}(v+1,i)+(\Delta v-\Delta u)\),与前者矛盾,证毕。

接下来就可以用分治来优化了。

定义 \(\operatorname{cal}(l,r,L,R)\) 为当前处理的区间 \([l,r]\) 和可能的最优决策点所在区间 \([L,R]\)。

对于一个这样的函数,我们可以暴力找到 \(mid=\left\lfloor l+r \right\rfloor\) 的最优决策点 p, 然后递归下去。

那么问题来了,怎么快速求出 \(\operatorname{val}(l,r)\) 呢?直接莫队就行了!

复杂度 \(O(kn \log n+n \sqrt n)\) 。

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 5, inf = LLONG_MAX >> 1;
ll n, k, a[N], cnt[N], lm = 1, rm = 0, ans = 0, f[N], g[N];
void add(ll w) {
	ans += cnt[a[w]];
	++cnt[a[w]];
}
void del(ll w) {
	--cnt[a[w]];
	ans -= cnt[a[w]];
}
ll val(ll l, ll r) {
	while (lm > l) add(--lm);
	while (lm < l) del(lm++);
	while (rm > r) del(rm--);
	while (rm < r) add(++rm);
	return ans;
}
void dfs(ll l, ll r, ll L, ll R) {
	if (l > r) return;
	ll mid = (l + r) >> 1, mid2 = L, minn = inf;
	for (ll i = L; i <= min(R, mid); ++i) {
		if (f[i - 1] + val(i, mid) < minn) {
			minn = f[i - 1] + val(i, mid);
			mid2 = i;
		}
	}
	g[mid] = minn;
	dfs(l, mid - 1, L, mid2); dfs(mid + 1, r, mid2, R);
}
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], f[i] = inf;
	for (ll i = 1; i <= k; ++i) {
		dfs(1, n, 1, n);
		for (ll j = 1; j <= n; ++j) f[j] = g[j], g[j] = inf;
	}
	cout << f[n] << endl;
	return 0;
}

标签:cnt,Minimization,val,题解,ll,Delta,rm,Problem,operatorname
From: https://www.cnblogs.com/HQJ2007/p/17561298.html

相关文章

  • 题解 P4322 [JSOI2016]最佳团体
    P4322[JSOI2016]最佳团体分数规划+树形背包。可以根据推荐关系建出一颗树,然后如果选了一点,则该点到根上的所有点都必须选。二分\(mid\),定义每个结点的权值,然后判断选\(k+1\)个节点的最大值是否大于\(0\)。设\(f_{i,j}\)为当前节点\(i\),在其子树内选了\(j\)个节点,最......
  • 题解 Bracket Insertion
    BracketInsertion神仙DP题,不愧是tourist。容易发现,括号序列一共有\(1\cdot3\cdot5...\cdot(2n-1)\)种生成方式。假如(为\(1\),)为\(-1\),那么一个序列合法的充要条件为:最小前缀和为\(0\),且以\(0\)结尾。现在考虑维护这些前缀和。如果我们在当前序列某一位后插......
  • 题解 P2276 [HNOI2002]农场的果树
    首先可以观察出一颗\(n\)个节点的二叉树,当其字典序最小的时候,其形态为一条向右偏的链,当其字典序最大的时候,是一条向左偏的链。由于每一种编码对应唯一的一颗二叉树,我们可以先建树。然后考虑树上分治,尝试以下三种方式:变大右子树的字典序变大左子树的字典序,并将右子树变成......
  • 题解 P7640 [BalticOI 2006 Day 2] CITY PLANNING
    首先我们定义“圈”为与原点距离相等的点集。...3.....323...32123.3210123.32123...323.....3...暴力:把圈放到堆里,然后每次取出代价最小的一圈,修改当前圈的楼层,向外圈拓展。正解:考虑二分。如果是二分最终答案,我们会发现......
  • 题解 P7250 [BalticOI 2012 Day1] 山峰
    通过观察,可以发现此题和最小生成树十分相似(两个地点之间途经的最小值最大)。于是可以考虑这么做:通过bfs将每一个块预处理出来,并记录其编号、高度、类型(是否为高地)以及边缘的点。将每一个块按高度从大到小排序。依次枚举每个块:对于当前要处理的块,枚举其边界的所有点,......
  • 题解 AT3726 [ARC087B] FT Robot
    首先可以观察到一个非常重要的性质:对于一次前进的操作,如果前面有奇数次转向,则走上下,否则走左右。(当然如果一开始就前进就只能走右)于是我们可以将其拆成许多的“块”,并分成两类,即前进方向为左右还是上下。然后对于两个维度分别dp。\(f_{i},_{j}=f_{i-1},_{j-val}\|\f_{i-......
  • Charles抓取https请求及常见问题解决
    一、背景APP测试的时候,通常都需要通过抓包工具抓取各类请求,查看接口的入参、返回值等,用于分析定位问题。常用的抓包工具有fiddler、charles等,抓取http的请求比较简单,https的请求稍显复杂。由于更喜欢charles的页面风格,本篇文章主要介绍以下两点:1、Charles如何抓取电脑端和手机端的......
  • CF1808C Unlucky Numbers 题解
    可以证明答案是\(l\)或\(r\)的一段前缀,拼上后面全部相同的一段字符\(d\),证明方式类似数位dp。能够自由填的数字一定是相等的,这样不会影响幸运值。前面那些不能自由填写的,就是\(l\)或\(r\)的一段前缀。假如不是\(l\)或\(r\)的一段前缀,必然填写相等的更好,而这种情况已......
  • P7809 [JRKSJ R2] 01 序列 题解
    前言传送门blog思路Problem1问题一问的是最长不下降子序列的长度,在一个$01$串中的最长不下降子序列,总共有三种$000\dots$,$000\dots111\dots$和$111111\dots$。可以把找到以上三种最长不下降子序列问题变为:$$\max^r_{i=l}(\sum_{j=l}^i[a_j=0])+(\sum_{j=i+1}^......
  • P7333 [JRKSJ R1] JFCA 题解
    前言传送门blog思路首先看数据范围$10^5$,$O(n\log_2n)$可以过,自然想到二分。二分具有单调性,那么如何确保整个$a$序列按顺序排列呢?我们可以使用st表维护区间最大值,如果在这个距离中已经有了$a_i\geb_j$那么最大值一定指向的是新加入进来的那个值,否则在之前二分就......