自己没办法独立想出来的会打*
思维训练以及算法巩固都是很重要的。
一眼网络流。
看 \(a\) 看着很难受,先取反,这样变成了 \(a>0\) 就有 \(a\) 的酒要给出,反之就是要收到 \(-a\) 的酒。
左右运输通常不大好搞,考虑能否都换成从左到右,若 \(i<j\),且 \(i\) 要运到 \(j\),即可以类图论的转为 \(i\to i+1\to i+2...\to j\) 的形式,其中权值为 \(+1\)。
若 \(i<j\),且 \(j\) 运到 \(i\),显然可以转为 \(i\) 运到 \(j\) 权值为 \(-1\) 的形式。
扫描线,记录正权和以及负权和,对当前是 \(a\) 的正负性,若 \(a>0\),那就说明需要从左边运过来 \(-a\) 的权值,倘若不够,就从转为正权值,即到右边再给出。负同理。在当前指针的增长时,正权和以及负权和都要通过一次运输,那么就要贡献上。。
写出来限制式子,一眼分开来变成裸贪心。。
拆行拆列的图论那一套想想。不难让 \((i,j)\) 变得有意义,即我们期望 \((i,j)\) 是能够满足让 \(i\) 匹配 \(j\) 的,弄成 \(2\) 层即可。
翻转都是翻转前缀,且对次数无最优限制。
不难想到第一个一定是最后一个翻转(其实不用),推过去,最大的就第一个翻转到最后一位。
于是想到从大到小确定后缀。其实这有点冒泡排序的思想在里面,在经过 \(i\) 轮后,\([n-i,n]\) 的数一定有序。再者从操作是影响前缀来看也可以想到从后缀开始确定。