Felicia
[动态规划]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 阅读(1478) 评论(3)  编辑 收藏 引用 所属分类: 动态规划
Comments

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


 
Powered by:
C++博客
Copyright © Felicia