首页 > 其他分享 >十连测 8C

十连测 8C

时间:2023-11-02 16:25:29浏览次数:36  
标签:8C 选取 当前 pair 代价 转移 dp 十连测

(私题)http://zhengruioi.com/contest/1485/problem/2734

容易想到 \(O(n^2)\) dp:设 \(dp_{i,j}\) 表示前 \(i\) 大的 \(x\) 与前 \(j\) 大的 \(y\) 所在的 pair 已被取走时的最小代价。转移时考虑第 \(i+1/j+1\) 大的 \(x/y\) 是否已经被取走,若是则不花费代价,否则花费对应代价即可。即钦定在第一次拿到某物品时花费代价。

但是这东西没什么优化空间啊!状态数卡的很死,且转移也不是很能优化。

考虑挖掘一些性质。

换个角度想,我们其实就是在钦定每个 pair 是选 \(x\) 还是 \(y\),只不过由于选法的特殊性,有一些选择的方式是不合法的。考虑按某种顺序依次考虑每一个 pair 的选取决策,寻找一些关于合法性的约束:

  • 若比当前 pair \(x\) 更大的 pair 还未选完,当前 pair 无法选择 \(x\)。

  • 若比当前 pair \(y\) 更大的 pair 还未选完,当前 pair 无法选择 \(y\)。

  • 若存在非偏序点对 \((a,b)\),设 \(a_x<b_x,a_y>b_y\),此时不能出现 \(a\) 选取 \(x\),\(b\) 选取 \(y\) 的决策。

发现前两条其实是没什么用的,第三条则是有关当前局面合法性的充要条件

考虑以 \(x\) 升序,设 \(dp_{i,j}\) 表示前 \(i\) 个 pair 选取后,选 \(x\) 的 pair 中最大的 \(y=j\) 的最小代价,此时若下一决策 \((x',y')\) 中的 \(y'>j\) 则可以该 pair 可以选取 \(y\) 或 \(x\),否则只能选取 \(x\)。此时有转移方程:

\[\begin{cases}dp_{i+1,j}=dp_{i,j}+x,&y\le j\\dp_{i+1,y}=dp_{i,j}+x,&y> j\\dp_{i+1,j}=dp_{i,j}+y,&y>j\end{cases} \]

我们发现该转移方程刚好是以 \(y\) 隔开的三段转移,用线段树维护即可,时间复杂度 \(O(n\log n)\)。

标签:8C,选取,当前,pair,代价,转移,dp,十连测
From: https://www.cnblogs.com/ydtz/p/17805665.html

相关文章

  • 十连测 8B
    (私题)http://zhengruioi.com/contest/1485/problem/2733见到环:断环成链。钦定第一组点的选取情况,其余点的选取不能越过该圆弧,故可以把链断开。剩余的每组点只剩下了最多两种选取决策,即中间点和靠前点构成圆弧,或中间点和靠后点构成圆弧。都和中间点有关,我们不妨以中间点为序依次......
  • CF708C Centroids
    对于一个不是重心的点\(u\),它必定有一棵子树\(T\)包含所有重心(如果有两个重心则它们必定相邻),显然\(|T|>\lfloor\frac{n}{2}\rfloor\),这阻碍了它成为重心。贪心地想,我们要在\(T\)中找出一棵子树\(S\)使得\(|S|\leq\lfloor\frac{n}{2}\rfloor\)且\(|S|\)尽可能大,然后将......
  • 【梦熊联盟】10月28日 NOIP十连测 第五场 题解
    目录T1男女排队简要题意:题解:T2树上最多不相交路径简要题意:题解:T3生日T4组队比赛简要题意:题解:T1男女排队简要题意:求长度为\(n\)的01序列不包含字串101或111的个数。\((n\leqslant10^{18})\)题解:一开始往容斥的思路去想,但是在推式子的时候发现其实很难容斥掉一个子串......
  • CF888C题解
    分析容易想到可以枚举每个字母,分别求其最小\(k\)取\(\min\)。思考对于一个\(k\),如何判其不合法。容易想到如果存在一个没有这个字符的长度大于等于\(k\)的子段,那么这个\(k\)就不合法。那么我们就知道如何求最小合法\(k\)了。找到最长的没有这个字符的子段,其长度加......
  • CF1868C Travel Plan 题解
    原题翻译发现所有长度相同的简单路径的权值可能情况相同,且最长的简单路径长度为\(O(\logn)\)级别,考虑维护所有长度的简单路径在一棵树上出现的次数,每种简单路径的权值在所有树上出现的次数,相乘即使答案。我们考虑长度为\(x\)的路径对答案的贡献,考虑枚举这条路径的贡献\(......
  • CF1168C And Reachability
    CF1168CAndReachabilityAndReachability-洛谷|计算机科学教育新生态(luogu.com.cn)目录CF1168CAndReachability题目大意思路code题目大意给定一个长度为\(n\)的数组\(a\)。你可以选择一个长度为\(k\)的数组\(p\)\(p_1=x,p_k=y\)当\(x<y\)且\(a_......
  • CF1168C
    CF1168C题面及数据范围Ps:链接为洛谷OJ。发现对于每一个\(i\)需要求经过若干次转移使第\(j\)个二进制位为\(1\)的最近位置\(k\),查询时,当\(k\leqy\)便可以到达。下文的位无特殊说明位均指二进制位。设\(f[i][j]\)为\(i\)经过转移使第\(j\)位为\(1\)的最近点......
  • 【原】电源集成INN3676C-H606-TL、INN3678C-H605-TL、INN3679C-H606-TL反激式电源转换
    1、简介InnoSwitch™3-EP系列IC极大地简化了反激式电源转换器的设计和制造,尤其是那些需要高效率和/或紧凑尺寸的产品。InnoSwitch3-EP系列将初级和次级控制器以及安全额定反馈集成到单个IC中。’InnoSwitch3-EP系列器件集成了多种保护功能,包括线路过压和欠压保护、输出过压和过......
  • [题解]CF1748C Zero-Sum Prefixes
    UPD23.10.3更新的对思路的描述,以及代码。思路对于每一个\(a_i=0\),如果我们将它变为\(x\),都可以直接将\(i\simn\)位置上的前缀和加\(x\)。设\(a_j\)是\(a_i\)后第一个\(0\),那么,在\(j\)时同样有上述规律。所以,我们只需在\(i\)时考虑,\(i\sim(j-1)\)的贡......
  • CF1878C Vasilije in Cacak 题解
    题目传送门简化题意有\(t\)组询问,每次询问是否能从\(1\simn\)中选择\(k\)个数使得它们的和为\(x\)。解法考虑临界情况,从\(1\simn\)中选择最小的\(k\)个数时和为\(\sum\limits_{i=1}^ki=\dfrac{(k+1)k}{2}\),从\(1\simn\)中选择最大的\(k\)个数时和为\(......