算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
A 水题不说
B 预处理前缀和
C 排序 Logn乱搞
D 动规
一开始你需要先处理出一条线段覆盖[l,r],且右端点恰好在r上的最小代价。这一步是O(n,m)。
然后dp[i][j]代表前i个hole修复j个的代价。
dp[i][j] = min(dp[i-1][j], dp[p][j - (i - p)] + cost[p+1, i]);

E 真乱搞
首先, ( a + b ) % m = m - 1 等价于 a + b = m - 1
(a + b) % m = m - 2 等价于  a + b = m - 2 ||  a + b = m*2 - 2
以此类推。。(m ^ 2) 会超时,咱们可以逐个数字搞

对于数字 m - 1 , 一定先和 0 搞(得 m - 1), 然后 m - 1 对搞 (得 m - 2)
对于数字 m - 2 , 一定先和 1 搞(得 m - 1), 然后和 0 搞 (得 m - 2), 然后和 m - 1搞(得 m - 3) 然后 m - 2对搞(得 m - 4) 
      
      。。。(召唤徐嘉大神传授乱搞算法)。。。

对于数字 m - i, 一定依次和 i - 1 .... 0 搞, 然后 m - 1 .... i 搞 
其实都是从右向左搞,如果可以直接略过值为0的数字,那么就会优化到O(m)。

这个可以用并查集维护都是“0”的线段。
posted on 2013-05-31 20:48 西月弦 阅读(370) 评论(0)  编辑 收藏 引用 所属分类: codeforces

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理