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