日韩一级大片在线,一本久道久久综合中文字幕,国产精品久久二区

PKU 1160 Post Office

/*
2

* File: 1160.cpp
3

* Author: GongZhi
4

* Problem: 動(dòng)態(tài)規(guī)劃四邊形優(yōu)化
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 閱讀(1367) 評(píng)論(1) 編輯收藏引用

評(píng)論

# re: PKU 1160 Post Office[未登錄](méi) 2009-12-11 16:46 intheway

Orz大牛. 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

# re: PKU 1160 Post Office[未登錄](méi) 2009-12-11 16:46 intheway

PKU 1160 Post Office

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(6)

隨筆檔案

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜