这题官方题解给了个Dilworth’s theorem，并不懂是什么东西。。。
写出来一些后可以找规律（多写），然后可以发现就是可以把原序列分成几块连续的上升序列，只不过块之间的相对顺序反了过来。。这个也不知道怎么证明，但是感觉是找不到比这个更好的。。这样的话就相当于LIS+LDS的长度是块的大小加上块的数量。实现的时候注意最后一个块可能不完整。
[CF][贪心] CF 1015D
http://codeforces.com/problemset/problem/1015/D
题意：给定n,k,s,要求在一段[1,n]的线段上走整点，从1开始，每次只能往一个方向走走任意步（但不能不动），然后要求总共走k步走完s，要求输出任意的方案。如果无法做到则输出NO。 继续阅读“[CF][贪心] CF 1015D”
[紫书][单调栈][思维] 求最大周长矩形 UVa12265
总感觉此题似曾相识，有很类似的求面积而非周长的题目？
题意给出长方形地图然后让求每个点对应的可贩卖的最大周长的矩形面积。考虑每一行的话，往上累计，然后就变成了一维的，在前面一些xx中求得最大/最小值的题，一般直接暴力会超时然后就用单调数据结构优化，这里左边每次动都相当于一个新的开始，所以就是添加和删除操作都在右侧进行，单调栈走起了。
继续阅读“[紫书][单调栈][思维] 求最大周长矩形 UVa12265”
[紫书][思维] 非常见模型 物理 思维与分析 UVa1442
紫书第八章这些题。。有点意思的啊。。
题意让往一个不规则的二维洞穴里面加水问每个地方都不碰到天花板的话最多能装多少水。当然很容易想到用在一点画一条横线然后与其他天花板不相交，但是没想出来怎么在低复杂度求和具体实现。看了紫书题解，才发现这条横线左右两边可以分开来求，这样求一边的时候就可以扫描一遍数组而不用O(n^2)去计算了， 继续阅读“[紫书][思维] 非常见模型 物理 思维与分析 UVa1442”