|
dp[l] = max(dp[l-1], dp[beg[j]]+to[j]-beg[j]) if to[j] == l
dp[l] = dp[l-1] else 很好理解的方程，优化。。只需要将数据按照to由小到大排序，然后决策就单调了，然后就没有然后了 排序是O(nlgn)，后面是摊还O(n)，总共O(nlgn) 用hash或者邻接表可以到O(n)。 |
|
细节啊
|
|
为什么O(n^2)的算法也可以过。。。。不科学
|
|
直接动规，果断慢成翔
|
|
为什么n^2跑了0.4s多。。 是评测机卡了么- -还是 sort太慢？
题目 33 [POI 1997] 阶梯教室设备利用
2013-10-30 14:02:17
|
|
线段的权值并非其长度，而是长度-1（因为有重叠）
|
|
函数好慢……
|
|
POI1997的题，好像还是山东的省选
|