摘要: 先預(yù)處理，把第i個(gè)村子到第j個(gè)村子中，建一個(gè)郵局的最小代價(jià)算出來(lái)，存在min_cost[i][j]里。
接下來(lái)就可以DP。設(shè)f[i][j]為前i個(gè)郵局，建在前j個(gè)村子的最小代價(jià)。那么f[i][j]可以轉(zhuǎn)移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代價(jià)是min_cost[j + 1][j + k]。

  閱讀全文      摘要: 簡(jiǎn)單題。很早以前做的。貼一下凌亂的代碼。

  閱讀全文      摘要: 簡(jiǎn)單的記憶化搜索。很早以前做的，代碼風(fēng)格很亂。將就一下啦。

  閱讀全文      摘要: 樓爺?shù)念}。遞推。f[n]表示n個(gè)結(jié)點(diǎn)的連通圖個(gè)數(shù)，則有遞推公式：

void calc(int n)
{
f[n] = 0;
for (int i = 1; i < n; i++)
f[n] += f[i] * f[n - i] * (pow(i) - 1) * C(n - 2, i - 1);
//pow(x) == 2^x
}

因?yàn)閿?shù)據(jù)較多，所以預(yù)先算出f[1] -- f[50]，再輸出。要用高精度。我用了標(biāo)程。

  閱讀全文      摘要: 首先明確一點(diǎn)：最優(yōu)解必為奶牛1..n-1輪流領(lǐng)跑，奶牛n撞線。且跑了x圈后，未領(lǐng)跑過(guò)的奶牛都耗費(fèi)了x的體力。
設(shè)f[i][j][k]表示前i-1頭奶牛已領(lǐng)跑，現(xiàn)在由第i頭奶牛領(lǐng)跑，一共跑了j圈，奶牛i耗費(fèi)了k的體力。
則f[i][j][k]可以轉(zhuǎn)移到f[i][j + p][k + p^2]（耗費(fèi)1分鐘，奶牛i以p圈/分鐘的速度繼續(xù)領(lǐng)跑），也可轉(zhuǎn)移到f[i + 1][j][j]（換成奶牛i + 1領(lǐng)跑，不耗費(fèi)時(shí)間）。
時(shí)間復(fù)雜度為O(nde^2.5)。

  閱讀全文      摘要: 感興趣的進(jìn)去慢慢看吧。

  閱讀全文      摘要: 推薦此題?；A(chǔ)樹型DP。
f[x][i](1 <= i <= p)表示以x為根的子樹，變成剩下i個(gè)點(diǎn)的子樹，且剩余子樹包含根結(jié)點(diǎn)，需要去掉的最少邊數(shù)。
那么父結(jié)點(diǎn)的f值可以由它所有的兒子的f值做背包得到。
最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])

  閱讀全文      摘要: 強(qiáng)烈推薦此題。樹型DP。
分析較長(zhǎng)且?guī)в袌D示，請(qǐng)閱讀全文。

  閱讀全文      摘要: 妹妹說(shuō)，難題得留著哥哥慢慢解，總會(huì)AC的。
聽著心里很是受用呢。

  閱讀全文      摘要: 強(qiáng)烈推薦此題。圖論和DP結(jié)合。
分析較長(zhǎng)，請(qǐng)閱讀全文。

  閱讀全文