3414如何记录区间信息如果要字典序最小那么应当尽可能选少的元素然后使其覆盖更大的区间和权重或许应当先考虑权重然后区间不覆盖是它的限制条件那么直接想到的思路就是按权重进行排序优先选择权重最大的四个使其满足区间不覆盖如果这样依然面对如何保留现有区间的问题以及如何在区间之间进行取舍就是说按右端点排序然后对于每个元素有选和不选两种情况如果要选的话由于是按右端点排序选的所以已有的数组当中右端点都不超过当前dp[i][j]是前i个里选j个区间的最好权重和如果选当前的那么应当是从j-1转移过来的然后还要求满足区间不覆盖所以之前选择的dp该比目前选择的第i个区间的左端点要短但是dp没保存选择的区间信息如何知道前面区间的最右端点信息就是说按右端点排序后往后递归时前面的区间一定不能超过当前选择区间的左端点然后由于是按右端点排的所以具有连续性所以可以二分搜索找到第一个不超过的下标p然后前面就都可以然后dp是说i区间之前最大的权重所以就直接是dp[p]就行那就是说对于第i个区间如果选择那就是在前面找p区间然后为dp[p][j-1]不选择那就是dp[i-1][j]两重循环最外层是j从2到4最里层就是i从头到尾初始化就是去选择i前确定j1时的最大权重不过对于数组元素为数组的排序如何操作即按右端点来排序这样加上一个a.r!b.r的判断能够在r相同时再对l进行排序但是还有一个问题dp是能找到权重的最优解但没保留下标的信息即最后即使知道了权重和最优是怎样的但该如何知道其对应的1872考虑动态规划最小子问题是在最右侧定义dp[i]为选择到i时与对手的最大差值从右侧到左侧生长对于每个数如果选择那么会得到此前所有数的和对于对手的最优选择就是dp[i1]即分数差为sum[i]-dp[i1](这里体现了dp中每个子问题的求解都是独立的)但这里sum是得分dp并不是得分而是分差应该不能直接计算如果不选择那么必然要在后面去选那最大分差就是dp[i1]为什么i1是否包含了后面的所有最优信息以及sum是说玩家在当前步骤中对i的选择所造成的得分但无法确定前面玩家是否已经得过分即sum是该步骤的得分而非玩家目前的总分还是考虑dp的干净定义即从i开始时目前玩家与对手所能得到造成的最大分差dp[i] 到底表示什么在标准解法里dp[i] 表示从状态 i 开始轮到当前玩家操作双方都最优时当前玩家相对于对手的未来分差。注意关键词未来分差。它不包括之前已经得过的分因为那些分已经固定对双方后续的最优决策没有影响。游戏是零和的后续决策只取决于当前剩下的石子状态。状态 i 的含义是· 前 i 个原始石子已经被合并成了一个新石子放在最左边· 这个新石子的值等于前缀和 P[i-1]· 剩下的原始石子是 stones[i..n-1]。所以干净定义dp后i天然就包含了i1及之后的最优情况