題目
第一題是一道數學問題
學過數學競賽的人一定知道對于這個問題
分得的所有數一定不是2就是3
而且2的個數<3
證明如下
顯然分成含有1的顯然不是最優的
若含有p(p>3)則可將其分成由2、3的和組成的序列保證其不差于此當前方案
第二題 一道維護決策單調性的DP
定義f[i][j]在前i個點建j個站前i個點以及建站的費用最小為多上
s[i][j] 為f[i][j]的方案
顯然s[i-1][j]<=s[i][j]<=s[i][j+1]
剩下的就不說了
posted on 2009-03-17 03:41
250 閱讀(479)
評論(0) 編輯 收藏 引用 所屬分類:
oi