国产精品老牛,宅男噜噜噜66一区二区66,欧美成人一区二区

[動態規劃]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]。

/*************************************************************************

Author: WHU_GCC

Created Time: 2007-9-3 22:18:48

File Name: pku1160.cpp

Description:

************************************************************************/

#include <iostream>

using namespace std;

#define out(x) (cout << #x << ": " << x << endl)

const int maxint = 0x7FFFFFFF;

typedef long long int64;

const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;

template <class T> void show(T a, int n) {for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }

template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 310;

int n, p;

int min_cost[maxn][maxn];

int f[maxn][maxn];

int a[maxn];

int main()

{

scanf("%d%d", &n, &p);

for (int i = 1; i <= n; i++)

scanf("%d", &a[i]);

for (int i = 1; i <= n; i++)

for (int j = i; j <= n; j++)

{

min_cost[i][j] = 0;

int mid = (i + j) / 2;

for (int k = i; k <= mid; k++)

min_cost[i][j] += a[mid] - a[k];

for (int k = mid + 1; k <= j; k++)

min_cost[i][j] += a[k] - a[mid];

}

for (int i = 0; i <= p; i++)

for (int j = 0; j <= n; j++)

f[i][j] = maxint;

f[0][0] = 0;

for (int i = 0; i <= p; i++)

for (int j = 0; j <= n; j++) if (f[i][j] < maxint)

{

for (int k = 1; j + k <= n; k++)

f[i + 1][j + k] <?= f[i][j] + min_cost[j + 1][j + k];

}

printf("%d\n", f[p][n]);

return 0;

}

posted on 2007-09-03 22:44 Felicia 閱讀(1526) 評論(3) 編輯收藏引用所屬分類: 動態規劃

Comments

# re: [動態規劃]pku1160
壓子
Posted @ 2007-09-07 11:59
謝謝回復更多評論
# re: [動態規劃]pku1160
ecnu_zp
Posted @ 2008-07-11 22:43
學習大牛..

^_^ 回復更多評論
# re: [動態規劃]pku1160
林志聰
Posted @ 2009-04-27 23:08
我想要的是算法、思想，不是代碼~~ 回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: [動態規劃]O(n^2 / logn)的LCS [動態規劃] pku1458 最長公共子序列 [動態規劃]pku1080 [動態規劃]pku1338 [動態規劃]pku3420 [動態規劃]pku1191 [動態規劃]pku1179 [動態規劃]pku1189 [動態規劃]pku1185 [動態規劃]pku1163

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

導航

常用鏈接

留言簿(22)

隨筆分類(145)

隨筆檔案(149)

相冊

ACMers

Pretty Girls

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜