摘要: 先預處理，把第i個村子到第j個村子中，建一個郵局的最小代價算出來，存在min_cost[i][j]里。
接下來就可以DP。設f[i][j]為前i個郵局，建在前j個村子的最小代價。那么f[i][j]可以轉移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代價是min_cost[j + 1][j + k]。
閱讀全文
摘要: 簡單題。很早以前做的。貼一下凌亂的代碼。
閱讀全文
摘要: 簡單的記憶化搜索。很早以前做的，代碼風格很亂。將就一下啦。
閱讀全文
摘要: 樓爺的題。遞推。f[n]表示n個結點的連通圖個數，則有遞推公式：
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
}
因為數據較多，所以預先算出f[1] -- f[50]，再輸出。要用高精度。我用了標程。
閱讀全文
摘要: 首先明確一點：最優解必為奶牛1..n-1輪流領跑，奶牛n撞線。且跑了x圈后，未領跑過的奶牛都耗費了x的體力。
設f[i][j][k]表示前i-1頭奶牛已領跑，現在由第i頭奶牛領跑，一共跑了j圈，奶牛i耗費了k的體力。
則f[i][j][k]可以轉移到f[i][j + p][k + p^2]（耗費1分鐘，奶牛i以p圈/分鐘的速度繼續領跑），也可轉移到f[i + 1][j][j]（換成奶牛i + 1領跑，不耗費時間）。
時間復雜度為O(nde^2.5)。
閱讀全文
摘要: 感興趣的進去慢慢看吧。
閱讀全文
摘要: 推薦此題。基礎樹型DP。
f[x][i](1 <= i <= p)表示以x為根的子樹，變成剩下i個點的子樹，且剩余子樹包含根結點，需要去掉的最少邊數。
那么父結點的f值可以由它所有的兒子的f值做背包得到。
最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])
閱讀全文
摘要: 強烈推薦此題。樹型DP。
分析較長且帶有圖示，請閱讀全文。
閱讀全文
摘要: 妹妹說，難題得留著哥哥慢慢解，總會AC的。
聽著心里很是受用呢。
閱讀全文
摘要: 強烈推薦此題。圖論和DP結合。
分析較長，請閱讀全文。
閱讀全文