SGU 183:好算法与差算法&好实现与差实现

看见SGU 183没有过,就想去过了他……条件:n=10000 m=100 time limit=250ms开始的时候,自己想了O(n*m^2)的算法,DP的,O(n*m^2)个状态,O(1)转移,太慢-2s……后来发现每次新的状态只有m个,其余都是原来的移位,于是通过修改,达到了O(n*m*logm)。其中,O(m*logm)是排序m个数的时间。这样是413ms,慢了一点…… 但是我想不到更快的排序方法了……于是就改变状态,像题解的那样,结果那样的O(n*m^2)需要4.xs… 改成O(n*m)的,结果还是超时,3xxms.. 正确的算法也需要优化啊……于是先优化,26xms,再优化,26xms,再优化,终于,只要23xms了…… 感觉平时写代码总是写得很烦,写得太复杂了。应该注重代码的简化……