题目链接题解：定义算上空格的前缀和\(sum[i]=\sum_{j=1}^{i}len[j]+1\)\(dp[i]=min_{j<i}(dp[j]+|sum[i]-sum[j]-1+L|^p)\)相当于枚举上一行的结尾在哪。可以感性理解一下，i越靠后，最优决策点j一定会往后移。所以决策点具有单调性。我有一个简单的证明，就是列个式子，证明i向后移

我们设\(s_i\)表示前\(i\)个句子的长度之和，这样就有dp\[f_i=\min_{j<i}\big\{f_j+|s_i-s_j+i-j-1-L|^P\big\}\]我们设\(w(l,r)=|s_r-s_l+r-l-1-L|^P\)，如果\(w\)满足四边形不等式，则原dp具有决策单调性。设\(u=(s_i+i)-(s_j+

这个题：二叉搜索树原理认识+区间dp；只要熟练相关算法就一定可以做出来。但我不行。。。我们学习一下笛卡尔树：什么垃圾东西，不学了。发现这个题是l蓝书上一道题jqb。二叉查找树又有一个性质：二叉查找树的中序遍历是其代表的序列从小到大排序的结果。而无论Treap如何旋转，其都

决策单调性#dp满足决策单调性，双端队列维护，可以二分出每两个限制的边界位置//Author:xiaruize#ifndefONLINE_JUDGEboolstart_of_memory_use;#else#definedebug(x)#endif#include<bits/stdc++.h>usingnamespacestd;#ifndefONLINE_JUDGEclock_tstart_clock=c

妙妙题#dp转换一下\(a_i^2\)，发现这个值等价于操作\(2\)次最后得到结果一样的方案数那么这就是容易的了\(dp_{k,i,j}\)表示操作了\(k\)轮，第一次的上面取了\(i\)个，第二次的上面取了\(j\)个转移分\(4\)种暴力就行注意空间限制要滚动//Author:xiaruize#ifndefO

Dinic#网络流#拓扑排序每个点向保护的点建图，对这个图拓扑排序，然后就是求这个图的最大完全子图，就是\(dinic\)板子//Author:xiaruize#ifndefONLINE_JUDGEboolstart_of_memory_use;#else#definedebug(x)#endif#include<bits/stdc++.h>usingnamespacestd;#ifnde

二分图最大匹配#贪心如果没有字典序最小的限制，直接二分图最大匹配就可以了考虑怎么让字典序最小倒序匹配左侧节点，对于每个节点，优先尝试字典序较小的方案，用hungary就行另，如果用费用流，需要将斐波那契的第\(10^4\)位作为费用//Author:xiaruize#ifndefONLINE_JUDGEbool

P1758[NOI2009]管道取珠看见方案数平方，考虑两个人分别取，两两匹配。P1912[NOI2009]诗人小G决策单调性，用队列维护。P1963[NOI2009]变换序列二分图+字典序，倒序考虑。P6843[BalticOI2015]FilePaths仔细读题，情况考虑全。P5861[IOI2015]teams分组先从最初的暴力贪

luoguP1963[NOI2009]变换序列题意对于\(N\)个整数\(0,1,\cdots,N-1\)，一个变换序列\(T\)可以将\(i\)变成\(T_i\)，其中\(T_i\in\{0,1,\cdots,N-1\}\)且\(\bigcup_{i=0}^{N-1}\{T_i\}=\{0,1,\cdots,N-1\}\)。，\(\forallx,y\in\{0,1,\cdots,N-1\

题意多测。给定\(n\)个字符串和一个常数\(L\)，试将这些字符串分成若干组，使得：令\(len(i)\)为第\(i\)个字符串的长度，则每组字符串的\(|\sum\limitslen(i)-L|\)

P1963[NOI2009]变换序列求最小字典序匈牙利算法进行匹配因为每一次是要求已经匹配好的人进行换对象如果从前面开始，那就是会要求前面已经匹配好的人换对象，答案就不一