POJ_1485

题目描述：

　　每组数据给n个点，点按一维坐标升序给出，要求划分成k块，在每一块中，取一个站，要求每个块中所有的点到站的距离的和的总和最小。

思路：

　　dp题，dp[i][j]表示i个点分成j块的最小距离，每一个dp[i][j]可以由前面的dp[x][j-1]推出，其中j-1 <= x <= i-1,前面j-1个分块再加上后面一块，便形成了i个点j个划分，在所有符合条件的划分中取最小值，更新dp[i][j]的值。这样的思路，我们还需要一个方法计算一个块中的距离最小值。当一个块中点的数量为奇数时，取中点为站，则距离最小，当数量为偶数时，去中间两个点的任意一个，距离最小，所以我们可以用(left+right)/2表示一个区间中的那个站点。因为结果要求输出最小值的具体划分以及站点，还需要一个pos数组储存每种情况的划分边界。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

#define MAX 1<<30;

int a[],dis[][],dp[][],pos[][][];

int main()

{

    int n,K,num = ;

    while(~scanf("%d%d",&n,&K) && n && K)

    {

        num++;

        memset(pos,,sizeof(pos));

        memset(dis,,sizeof(dis));

        for(int i = ;i <= n;i++)   scanf("%d",&a[i]);

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

        {

            dis[i][i] = ;

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

            {

                int mid = (i+j)/;

                for(int k = i;k < mid;k++)  dis[i][j] += a[mid]-a[k];

                for(int k = mid+;k <= j;k++)   dis[i][j] += a[k]-a[mid];

            }

        }

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

        {

            dp[i][] = dis[][i];

            pos[i][][i] = ;

            for(int j = ;j <= i;j++)   dp[i][j] = MAX;

        }

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

        {

            for(int j = ;j <= min(i,K);j++)

            {

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

                {

                    int temp = dp[k][j-]+dis[k+][i];

                    if(temp < dp[i][j])

                    {

                        dp[i][j] = temp;

                        for(int l = ;l <= k;l++)

                        {

                            pos[i][j][l] = pos[k][j-][l];

                        }

                        pos[i][j][i] = ;

                    }

                }

            }

        }

        printf("Chain %d\n",num);

        int now = ;

        for(int i = ;i <= K;i++)

        {

            int left = now;

            for(;!pos[n][K][now];now++);

            int right = now++;

            if (left == right)

            {

                printf("Depot %d at restaurant %d serves restaurant %d\n",i,left,left);

            }

            else

            {

                printf("Depot %d at restaurant %d serves restaurants %d to %d\n",i,(left+right)/,left,right);

            }

        }

        printf("Total distance sum = %d\n\n",dp[n][K]);

    }

    return ;

}

巴特西

POJ_1485_dp

最新文章

热门文章