久久国产视屏,久久激情五月丁香伊人,蜜桃麻豆www久久国产精品

PKU 1160 Post Office

/*
2

* File: 1160.cpp
3

* Author: GongZhi
4

* Problem: 動態規劃四邊形優化
5

* Created on 2009年7月27日, 上午12:00
6

*/
7

#include <stdlib.h>
9

#include <string.h>
10

#include <iostream>
11

#include <string>
12

#include <vector>
13

#include <map>
14

#include <queue>
15

using namespace std;
16

/*
18

*
19

*/
20

#define MAXN 2000
21

int a[MAXN], sum[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];
22

int main() {
24

int n, m, i, j, t, k;
25

scanf("%d%d", &n, &m);
26

for (i = 1; i <= n; i++)scanf("%d", &a[i]);
27

sum[0] = 0;
28

for (i = 1; i <= n; i++)sum[i] = sum[i - 1] + a[i];
29

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

for (j = 1; j <= n; j++) {
31

t = (i + j) / 2;
32

w[i][j] = (t - i + 1) * a[t]-(sum[t] - sum[i - 1]) +(sum[j] - sum[t - 1])-(j - t + 1) * a[t];
33

}
34

for (i = 1; i <= n; i++) {
35

f[1][i] = w[1][i];
36

p[1][i] = 1;
37

}
38

for (i = 2; i <= m; i++) {
39

j = n;
40

f[i][j] = 1000000000;
41

for (k = p[i - 1][j]; k <= j - 1; k++)
42

if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
43

f[i][j] = f[i - 1][k] + w[k + 1][j];
44

p[i][j] = k;
45

}
46

for (j = n - 1; j >= 1; j--) {
47

f[i][j] = 1000000000;
48

for (k = p[i - 1][j]; k <= p[i][j+1]; k++)
49

if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
50

f[i][j] = f[i - 1][k] + w[k + 1][j];
51

p[i][j] = k;
52

}
53

}
54

}
55

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

return 0;
57

}
58

posted on 2009-07-27 00:56 gong 閱讀(1356) 評論(1) 編輯收藏引用

統計

隨筆 - 50
文章 - 0
評論 - 22
引用 - 0

常用鏈接

留言簿(6)

隨筆檔案

搜索

積分與排名

積分 - 28325
排名 - 672

# re: PKU 1160 Post Office[未登錄] 2009-12-11 16:46 intheway

PKU 1160 Post Office

評論

導航

統計

常用鏈接

留言簿(6)

隨筆檔案

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

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



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