PKU 1160 Post Office

 1/* 
 2 * File:   1160.cpp
 3 * Author: GongZhi
 4 * Problem: 动态规划 四边形优化
 5 * Created on 2009年7月27日, 上午12:00
 6 */
 7
 8#include <stdlib.h>
 9#include <string.h>
10#include <iostream>
11#include <string>
12#include <vector>
13#include <map>
14#include <queue>
15using namespace std;
16
17/*
18 *
19 */
20#define MAXN 2000
21int a[MAXN], sum[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];
22
23int 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
59
60

posted on 2009-07-27 00:56 gong 阅读(1336) 评论(1)  编辑 收藏 引用

评论

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

Orz大牛.  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2008年7月>
日一二三四五六
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜