紫书第八章这些题。。有点意思的啊。。
题意让往一个不规则的二维洞穴里面加水问每个地方都不碰到天花板的话最多能装多少水。当然很容易想到用在一点画一条横线然后与其他天花板不相交，但是没想出来怎么在低复杂度求和具体实现。看了紫书题解，才发现这条横线左右两边可以分开来求，这样求一边的时候就可以扫描一遍数组而不用O(n^2)去计算了， 继续阅读“[紫书][思维] 非常见模型 物理 思维与分析 UVa1442”
紫书第八章这些题。。有点意思的啊。。
题意让往一个不规则的二维洞穴里面加水问每个地方都不碰到天花板的话最多能装多少水。当然很容易想到用在一点画一条横线然后与其他天花板不相交，但是没想出来怎么在低复杂度求和具体实现。看了紫书题解，才发现这条横线左右两边可以分开来求，这样求一边的时候就可以扫描一遍数组而不用O(n^2)去计算了， 继续阅读“[紫书][思维] 非常见模型 物理 思维与分析 UVa1442”