poj 1160 post office------DP

題目大意：

 有一條筆直的公路，每個村莊的位置被确定為一個單一的整數坐标。在同一位置上沒有兩個村莊。兩個位置之間的距離是它們的整數坐标的內插補點的絕對值。郵政局将建立在一些村莊，但不一定是所有的。一個村莊和郵局有相同的位置。對于建立郵政局，應選擇他們的位置，使每個村和它最近的郵局之間的所有的距離的總和最小。你要寫一個程式，給出了村莊的位置和郵局的數量，計算出所有距離最小的總和。

算法： DP，預處理比較重要。

變量解釋：s[i][j]:兩點(i,j)間的距離；c[i][j]:兩點(i,j)之間建一個郵局（包含端點）的最優解；f[i][k]:前i個點建k個郵局的最優解；

代碼實作：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int f[305][35],s[305][305],c[305][305];
int main()
{
	int n,m;
	int a[305];
	memset(c,0,sizeof(c));
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++)
        	s[i][j]=a[j]-a[i],s[j][i]=s[i][j]; 
	for (int i=1;i<=n;i++)
    	for (int j=i+1;j<=n;j++)
    	    for (int k=i;k<=j;k++)
	        {
	        	int mid=(i+j)/2;
	        	c[i][j]+=s[k][mid];
			}   //直覺表明，兩地之間建一個郵局，建在中間村莊最優；
	memset(f,0x3f,sizeof(f));
	for (int i=1;i<=n;i++) f[i][1]=c[1][i];
    for (int k=2;k<=m;k++)
        for (int i=2;i<=n;i++)
            for (int j=k-1;j<=i-1;j++)
            {
            	if (f[j][k-1]+c[j+1][i]<f[i][k])
            	  f[i][k]=f[j][k-1]+c[j+1][i];
			}
    printf("%d",f[n][m]);
    return 0;
}