題目
第一題是一道數(shù)學(xué)問題
學(xué)過數(shù)學(xué)競賽的人一定知道對于這個問題
分得的所有數(shù)一定不是2就是3
而且2的個數(shù)<3
證明如下
顯然分成含有1的顯然不是最優(yōu)的
若含有p(p>3)則可將其分成由2、3的和組成的序列保證其不差于此當(dāng)前方案
第二題 一道維護(hù)決策單調(diào)性的DP
定義f[i][j]在前i個點建j個站前i個點以及建站的費用最小為多上
s[i][j] 為f[i][j]的方案
顯然s[i-1][j]<=s[i][j]<=s[i][j+1]
剩下的就不說了