dp的优化众多，但用图论模型去解决实在巧妙。
BZOJ 1981: [Google Codejam2010]Fence
用剩余类加spfa解决。由于L特别大所以可以这么搞。
http://cdqz.openjudge.cn/2015/1014/
dp方程为：f[i]=min(f[j-1]+abs((i-j)-a[j]),1<=j<=i。
最朴素实现为O(N^2)。
可以将绝对值打开，用线段树维护，复杂度为O(NlogN)。但还是被卡掉了。
假设我们当前读入到I，那么我们不妨先假设i只能到i+a[i]+1（代价为0），这时候我可以往前和往后走（代价为1)。
将其抽象成一张图，从0开始走那么dis[n]即为答案。
由于点数和边数均为线性，且边权为0/1，可以用bfs在O(N)时间内解决。
注意判a[i]较大的情况即可。
CF 280D - k-Maximum Subsequence Sum
朴素DP由于是类似卷积的合并，套上线段树是K^2NlogN的。
仿照网络流的做法，每次找一段最大的子序列，然后取反，继续做，每次询问结束后恢复。这样显然是KNlogN的。（用c++ pair爽死）