要求给一片文章排版，要求每行 $W$ 个格子，每一行的要求是首单词必须顶格，除了最后一行之外的尾单词也必须顶格，然后单词之间至少有 $1$ 个空格，单词内部不能有空格，也不能改变单词之间的顺序。现在问在排版方案满足这些要求的条件下，单词之间的最大空格最小是多少。数据量: 每一行的格子数： $3\le W \le 80,000$， 总共的单词数：$2\le N\le 50,000$ 每个单词的长度 $x_i$ 满足 $1\le x_i \le \frac{W-1}{2}$
继续阅读“[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing”
这次学校网络赛还是挺不错的，有3道题（F I J）都是值得一做的emm，J题胡乱暴力+dp拿了个一血，I题胡乱暴力也过了
当然由于我FFT/NTT&斯特林数学的不行所以F题并不会做，虽然推出来公式和dalao一样但是没法把复杂度降下去，等到学会了应该会放个F的题解
J题吧，跟UVa 437 The Tower of Babylon很像，当然只是看上去很像，UVa 437的限制是每种箱子必须叠在比他严格小的另一个上，然后箱子无限用，XDOJ 1420 是叠在长宽大于等于该箱子的另一个箱子上，但是每种箱子只能用一次。
如果箱子的数量少一点的话，其实完全可以直接完全状态压缩动态规划，但是这题数量是30，压缩成二进制的话2^30肯定会超时，所以需要一点操作。。
首先先全部暴搜，dfs(x,S)表示当前以箱子x号为最底部箱子，之前已经用过的也就是还在x更底下的箱子情况为S（S是一个十进制数，展开成01二进制串表示30个箱子是否被使用过）所能达到的最高的高度，每次都打一遍结果，很快可以发现，当取到某一个箱子之后，在某些情况下他后面的搜索路径就是固定的。
就比如说 某次搜到了箱子3，然后他之后的搜索路径就只能放箱子6和7，然后把每次搜索路径都打出来就会发现，其实之后的每次搜到3都会是走6和7，除非6和7之前已经被用过了也就是说6或7变成了3底下的箱子，这时候后面的路径会发生一些变化，因为每个箱子只能用一次。（这里本该举一组样例但我实在找不到当时画的样例了emm）
然后到这里就可以想一下是不是可以用这个特性对dfs(x,S)进行剪枝和记忆化搜索，首先把S的定义反转，让S这个二进制数表示尚未使用过的箱子”的情况，比如00101表示1号和3号箱子还没有被用过，245号箱子已经被用过了。这样的话，每次dfs的时候可以记录下来一个dp(x,TS)的记忆化结果，其中TS是S和“理论上可以放到x上的所有箱子的集合”KS相与的结果，这里后者可以n^2复杂度枚举预处理，我的代码里是存储到ky[x]的数组里。这样的话，每次dfs就是先把TS求出来，然后判断(x,TS)这个对有没有在之前被搜索过，如果有的话就直接返回结果，这里的这个结果可以用一个map<pair<int,int>, int> 来保存，如果没有出现过的话的话就直接暴搜，这样的话每种箱子作为底的每种情况只会被搜到一次，就等于提前把绝不可能走到的箱子和已经走过的路径都剪掉了。把所有的状况想象成图的话，每个箱子三种形态那就是有90个节点，每个结点出发能走的最长的路径最多30个，如果能保证每种情况只走一次其实是相当快的（主要是我并不会严格证明复杂度emmm）
我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去
直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 继续阅读“[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983”
