poj1161Post Office【经典dp】

今天药忘吃喽~ 2022-08-10 15:57 173阅读 0赞

题目：poj1161Post Office[点击打开链接][Link 1]

题意：给出一条直线上的n个坐标表示村庄的位置，然后要在上面建p个邮局，村民优先选择去近的邮局，问所有村庄去邮局的最小距离和是多少？

分类：区间dp

分析：对于任意一个村庄，只有两种选择，要么在这儿建邮局，要么不建，我们可以预处理出来任意两件建立一个邮局的的最小距离w【i】【j】，而对于任意两点，建立一个邮局的最优方案是建立在两点的中位数上，即（i+j）/2，位置。

对于任意两点 i---j ，建立两个邮局的最优结果我们可以由建立一个的得到，枚举分点，然后从中间分开，前面建一个，后面建一个。那么我们就可以写出状态及方程

定义状态:dp【i】【j】表示在前 i 个存在建立 j 个邮局的最小距离。

转移方程：dp【i】【j】=min（dp【i】【j】，dp【k】【j-1】+w【k+1】【i】） （j-1<=K<=i-1）

注意：

1：这个题目的dp方向是邮局数目，不是村庄数目，有建立邮局的数目1----p的方向dp

2：注意dp初始化后，其他值一定在循环内部初始化，否则不一定最优、

代码：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <map>
    #include <cmath>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 500;
    int w[N][N];
    int dp[N][45];
    int dis[N];
    
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            for(int i=1;i<=n;i++)
                scanf("%d",&dis[i]);
            Del(w,0);
            for(int i=1;i<=n;i++)
            {
                for(int j=i+1;j<=n;j++)
                {
                    w[i][j] = w[i][j-1]+  dis[j]  -  dis[(i+j)/2];
                }
                //printf("\n");
            }
            Del(dp,0x3f3f3f3f);
            for(int i=1;i<=n;i++)
            {
                dp[i][1]=w[1][i];
                dp[i][i]=0;
            }
            for(int j=2;j<=k;j++)
            {
                for(int i=j+1;i<=n;i++)
                {
                    dp[i][j]=0x3f3f3f3f;//注意标准写法
                    for(int f=j-1;f<=i-1;f++)
                        dp[i][j]=min(dp[i][j],dp[f][j-1]+w[f+1][i]);
                }
            }
            printf("%d\n",dp[n][k]);
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1160