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 阅读(1310) 评论(1) 编辑收藏引用

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

Orz大牛. 回复更多评论

刷新评论列表

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2024年4月

日

一

二

三

四

五

六

统计

随笔 - 50
文章 - 0
评论 - 22
引用 - 0

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

积分 - 27127
排名 - 675

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