把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

正文

浅谈一下我理解的四边形不等式
题目有POJ 1160 ,HDU 2829，HDU3480（或许之后还可以补充）
这几题题目大意基本是求把一段东西分成m段东西使之某种价值的和最小，而一段区间的这个东西的价值可以用w(i,j)表示，这个w(i,j)拥有四边形不等式的性质（是什么性质自己百度捏），那么如果是形如区间dp[i][j]=min(dp[i][k]+dp[k+1][j])+w(i,j)（因为是定值放不放在括号内无所谓）的转移式子，那么这个时候dp同样具有四边形不等式的性质，当dp具有四边形不等式的性质，并且具有区间单调性（包含在一个区间内的区间值比包含着它的区间的值小）的时候，dp[i][j]的割点（设为sup[i][j]）一定在sup[i+1][j]到sup[i][j-1]之间（略过证明，看似麻烦其实写写就证出来了），而每一轮的sup范围之和不会超过2n，所以把O(n3)转化为了O(2n2)。
个人的理解为四边形不等式实际上是斜率dp的一种特殊情况（w满足四边形不等式且区间满足单调性下的特殊情况），为什么呢？因为优化的方向相同，还记不记得斜率dp的凸包中会放有至少两个端点，而四边形每一轮的sup范围之和也是2n左右，为什么呢？因为无论是斜率还是四边形都无法确定在一个合格凸包中最优的到底是哪个，所以无论是哪种优化方式都无法真正优化到O(1)，四边形只是在斜率的基础上把凸包的总大小严格缩小到了2n，所以说是在满足条件下的特殊的斜率优化。
注意这里的dp[i][j]并不一定真正表示的是题目中区间，正如标题上提到的三道题中就不是，在这些题中dp[i][j]表示的是当前分割到i段且结尾为j时最小的价值和，而为什么dp[i][j]依然可以用四边形优化呢？因为它同样满足区间单调性和形如上述一样的转移方程（虽然更加简单），这说明了四边形不等式不仅可以作用于区间dp，而是可以服务于更加抽象的东西，只要dp和w之间满足上述关系就可以用四边形不等式优化。当然，对于不同的题目来讲初态的设置也值得赋予不同程度的注意（这些题中i都是倒序遍历（因为用到了i+1），而且由于四边形不等式的抽象性，出现了i>j（段数大于原本长度）时的值这种毫无实际意义的数据，而类似石子合并的四边形不等式就是正向并且按照区间长度顺序去遍历，一定要注意初态、转移、边界的区别）。

题解就放HDU3480的了，个人觉得相当具有代表性。
大意：给一个数集（大小为1e4），要求分为m段（大小为5k），使得每个集的max-min的平方和最小。
由于集合的价值w[i][j]难以直接求出，所以先去想怎么优化题目数据。
集合并不一定要连续，也就是我可以任意排序之后求区间和，那么对这题来说，可以很容易地推出当所有数据顺序排列时区间和一定是最小的，并且大小相当于区间最后一个数减最前一个数的平方。
推出了w[i][j]之后去推dp，容易发现dp[i][j]=dp[i-1][k]+w[k+1][j]，为什么说这个东西可以用于上面的四边形不等式呢，这里我们把dp扩展一维，dp[i][j]=dp[i][1][j]，w[k+1][j]看成dp[1][k+1][j]，原来的区间合并就相当于dp[i][1][j]=min(dp[i-1][1][k],dp[1][k+1][j])+w[i][j]，这里w[i][j]=0，因为显然合并区间没有任何的价值，到这是不是就明白为什么非区间的dp[i][j]可以靠四边形不等式优化？
但原式中的dp[i][j]是从dp[i-1][k]推上来的呀，用于操作不等式的sup[i+1][j]有什么用呢？就是没用，到这一步之后，整个dp的转移以及只剩下代数意义而没有实际意义了，这点也和斜率dp相同，既然原式已经被转移成了代数性质，那么只要当成代数就行，不需要再去纠结实际意义，那么原本没有意义的sup[i+1][j]是什么呢？是1到n里面的割点，哦，那设置成n就好了，注意千万不要设置为j，时刻提醒自己这个式子中的数已经全都没有实际意义了。