HDU 1227 Fast Food

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1227

题意：一维坐标上有n个点，位置已知，选出k(k <= n)个点，使得所有n个点与选定的点中最近的点的距离总和最小，求出最小值。

思路:

将点i的距离记为为dis[i]，从i到j选出一点使此段距离和最小，则此点坐标为dis[(i + j) / 2]

cost[i][j]为从i到j选出一点距离和的最小值。则求cost[i][j]的代码如下：

　　cost[i][j] = 0;
　　for(int k = i; k <= j; k++){
　　　　cost[i][j] += abs(dis[(i + j)/2] - dis[k]);
　　}

dp[i][j]表示从1到i选择j个点的最小值，则状态转移方程如下：

dp[i][j] = min(dp[k][j - 1] + cost[k + 1][i]) (j - 1 <= k <i)

代码如下，注意边界情况的处理，表示我也很头疼边界情况

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long LL;

const int N = ;

LL dp[N][], cost[N][N];

int dis[N];

int main(){

    int n, m, cs = ;

    while(~scanf("%d %d", &n ,&m) && n && m ){

        for(int i = ; i <= n ; i++){

            scanf("%d", &dis[i]);

        }

        memset(cost, 0x3F, sizeof(cost));

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

        for(int i = ; i <= n ; i++){

            for(int j = i; j <= n ;j++){

                cost[i][j] = ;

                for(int k = i; k <= j; k++){

                    cost[i][j] += abs(dis[(i + j)/] - dis[k]);

                }

            }

        }

        for(int i = ; i <= n; i++){

            dp[i][] = cost[][i];

        }

        for(int j = ; j <= m ; j++){

            for(int i = j; i <= n; i++){

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

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

                }

            }

        }

        cs++;

        printf("Chain %d\nTotal distance sum = %I64d\n\n",cs,dp[n][m]);

    }

    return ;

}

巴特西

HDU 1227 Fast Food

最新文章

热门文章