Felicia

2007年9月3日

[动态规划]pku1160
     摘要: 先预处理，把第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]。

  阅读全文
posted @ 2007-09-03 22:44 Felicia 阅读(1478) | 评论 (3) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia