国家集训队作业命题wqs

1、能量棒哈尔滨市第三中学 王钦石给定一个长为N的正整数列A，分成K段，定义每段的价值为 x2+Bx+C，其中x为这一段的和，求最大的总价值。K=N=105题目大意记每段和为Si，则总价值为(-Si2+BSi+C)，可以变形为-Si2+BSi+CK = -Si2+BAi+CK，后两项都是与决策无关的，所以只需求出Si2的最小值不经这步简化，下述所有算法稍加修改均仍可用，不过编码难度将有所增加以下将以求最小平方和为问题进行求解分析枚举分段方案，计算每个方案的答案，求最小值。时间复杂度：O(NK)期望得分：510分算法一显然可以进行动态规划记fij为将前i个数分成j段所能获得的最小平方和，枚举最后一段

2、的长度进行转移转移方程fij = minfkj-1+(Ak.i-1)2时间复杂度O(N3K)，期望得分15分可以使用前缀和快速计算出Ak.i-1时间复杂度O(N2K) ，期望得分2025分算法二转移方程满足四边形不等式记pij为计算fij时取到最优值的最小的k有pi-1jpij pij-1先计算fi-1j和fij-1，并记录p值计算fij时只需检查k在区间pi-1j, pij-1的情况即可对于每个x，所有i+j=x的fij只需检查O(N)次时间复杂度O(N2)期望得分40分算法三记A中前i个数的和为Si转移方程fij = minfkj-1+(Si-Sk)2变形为fij = minfkj-1+S

3、i2+Sk2-2SiSk按j从小到大计算，将每个fkj-1看做平面上一个点(Sk , fkj-1+Sk2)，每次找出y-2Six最小的点凸壳！O(N)扫描求出凸壳，由于S是递增的，可以扫描一次求出每个i的答案时间复杂度O(NK)，期望得分50分算法四通过一些手段剪掉不优的状态，减小计算量缺点是时间复杂度/解的最优性没有保障得到高分需花费较多时间较好情况下期望得分5080分非完美算法考虑这样一个问题，把一个数列分成若干段(不限定段数)，使平方和最小，但是每分一段需要额外C的代价，即每段的代价是x2+C使用动态规划，fi表示前i个数分若干段的最小总代价可以使用算法四中的方法进行优化时间复杂度O(N

4、)算法五当C值增大时，最优解的段数会减小二分！二分C的大小，动态规划求解时记录最优解分的段数找到合适的C值，计算出上述问题的答案减去CK即为原问题答案时间复杂度O(NlogC)期望得分100分算法五这里有一个问题C不存在怎么办？为了解决这个问题，我们在求解固定C值的问题时需要找到最优解中分段数最少的一个，这可以在动态规划过程中控制如果C取某一值时分段数过少，-1后又过多，那么直接取此C值的答案减CK算法五对于一个固定的数列A，不同K值时的答案记做ans(K)那么点(K, ans(K)会形成如下形态可以证明，不存在合适C值的点一定如箭头所示即(K, ans(K)形成的点集是凸的算法五一年多前思考

5、斜率优化的应用注意到定义每段代价为x2+C，则C越大，所分的段数越少想到二分C来求解限制分段数的问题考虑不存在合适C值的情况证明(K,ans(K)形成的点集一定是凸的加一点小包装：求解最大化-x2+Bx+C设置题目背景命题思路斜率优化可以扩展为更普通的单调性优化所以可以把每一段的价值改为更为复杂的函数不过这样仅仅是增大了问题的复杂程度尽量使问题简洁优美，没有这样设计命题思路我写了3个不同的生成器并用统一的接口来调用gen(int N, int v)N为序列的长度，v为数值的期望genA为在1,2v-1中等概率选择一个数genB为将每100个数分为一段，每段有50%的概率在1,v-1中随机产生，50%的概率在v+1,2v-1中随机产生genC为每个数有0.1%的概率在1,1001v-1中产生，否则在1,v-1中产生数据设计前10个测试点全部由genA生成其余10个有2个为ABB，2个ACC，其余为ABC命题时我曾考虑提供数据生成器供测试非完美算法，这样区分度会更好无法阻止选手获得输入数据，没有成功数据设计得分分布(NOI正式选手)得分分布(60人集训队选手)感谢CCF给我提供这次的机会感谢父母对我的养育感谢张海峰老师对我的指导感谢两位教练和多位大牛对我的帮助感谢学校对我的支持感谢谢谢大家欢迎提问记dij为f