山区建小学（区间dp+前缀和+预处理）

【题目描述】

　　　　政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。

【题目链接】

　　　　http://noi.openjudge.cn/ch0206/7624/

【算法】

定义dp[i][j]为前i个村庄建j个小学，构建状态转移方程为dp[i][j] = min(dp[i][j], dp[k][j] + cost[i+1][j]) 其中cost[i][j]表示第i个村庄到第j个村庄建一个小学的最短距离和
预处理cost数组，众所周知，满足最短距离和的小学应该建在中位数的村庄处，同时也满足递推关系：cost[i][j] = cost[i][j-1] + dist[j] - dist[i+j>>1]
前缀和就是村庄所处位置

【代码】

#include <iostream>

#include <stdlib.h>

#include <algorithm>

#include <cstring>

using namespace std;

int m,n,i,j,k;

int dist[],cost[][],dp[][];

int main()

{

    cin>>m>>n;

    dist[]=;

    for(i=;i<=m;i++)

        cin>>dist[i],dist[i]+=dist[i-];

    for(i=;i<=m;i++)

        for(j=i+;j<=m;j++)

            cost[i][j]=cost[i][j-]+dist[j]-dist[i+j>>];

    memset(dp,0x7f,sizeof(dp));

    for(i=;i<=m;i++) dp[i][]=cost[][i];

    for(i=;i<=m;i++)

        for(j=;j<=min(i,n);j++)

            for(k=j-;k<i;k++)

                dp[i][j]=min(dp[i][j],dp[k][j-]+cost[k+][i]);

    cout<<dp[m][n];

    return ;

}

巴特西

山区建小学（区间dp+前缀和+预处理）

最新文章

热门文章