♥Vijos 1242-邮局问题【经典DP】

梦里梦外; 2022-08-20 04:21 165阅读 0赞

**P1242**邮局问题

[Accepted][]

标签： [IOI2000][] \[显示标签\]

## 描述 ##

一些村庄建在一条笔直的高速公路边上，我们用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。

数据规模：1<=村庄数<=300, 1<=邮局数<=30, 1<=村庄坐标<=10000

## 格式 ##

### 输入格式 ###

2行

第一行:n m \{表示有n个村庄，建立m个邮局\}  
第二行:a1 a2 a3 .. an \{表示n个村庄的坐标\}

### 输出格式 ###

1行

第一行:l \{l表示最小距离总和\}

## 样例1 ##

### 样例输入1\[复制\] ###

>     10 5
>     1 2 3 6 7 9 11 22 44 50

### 样例输出1\[复制\] ###

>     9

## 来源 ##

IOI2000' 第五题

解题思路：

**给定一个序列,假设我们要建一个邮局,那么一定是在这个序列的中点,所以我们可以先预处理出序列区间\[l,r\]之间建立**

**一个邮局的最短距离和w\[l\]\[r\],然后用dp\[i\]\[j\]表示到i个村庄建立j个邮局的最短距离和,那么就有状态转移方程:**

dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[k\]\[j-1\]+w\[k+1\]\[i\]);

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #define INF 0x3f3f3f3f
    using namespace std;
    int w[400][400];
    int dp[400][400];
    int a[400];
    int n,m;
    
    void Init(int a[],int n)
    {
    	memset(w,0,sizeof(w));
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=i+1;j<=n;j++)
    		{
    			w[i][j]=w[i][j-1]+a[j]-a[(i+j)>>1];
    		}
    	}
    }
    
    int work()
    {
    	int i,j,k;
    	for(i=1;i<=n;i++)
    	{
    		dp[i][i]=0;
    		dp[i][1]=w[1][i];
    	}
    	for(j=2;j<=m;j++)
    	{
    		for(i=j+1;i<=n;i++)
    		{
    			dp[i][j]=INF;
    			for(k=j-1;k<i;k++)
    			{
    				dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i]);
    			}
    		}
    	}
    	return dp[n][m];
    }
    int main()
    {
    	while(scanf("%d%d",&n,&m)!=EOF)
    	{
    		int i,j;
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		Init(a,n);
    		printf("%d\n",work());
    	}
    	return 0;
    }

[Accepted]: https://vijos.org/records/56ac741417f3cab017292937
[IOI2000]: https://vijos.org/p/IOI+2000