poj1160——Post Office//dp

动态规划还是最无语的一块~ 参见：http://zebozhuang.blog.163.com/blog/static/1714798042010107104459174/

#include<iostream>
#include<cstdio>
#include<string>
#include<math.h>
using namespace std;
#define maxn 305
#define maxcost 9999999
int w[maxn][maxn],m[maxn][maxn],d[maxn];
int min(int a,int b)
{
	if(a>b) return b;
	return a;
}
int main()
{
	int i,j;
	int v,p;
	cin>>v>>p;
	for(i=1;i<=v;i++)
	{
		scanf("%d",&d[i]);
	}
	for(i=1;i<=v;i++)
		for(j=1;j<=v;j++)
		{
			int mid=(i+j)/2;
			for(int k=i;k<=j;k++)
				w[i][j]+=abs(d[k]-d[mid]);
		}
		for(i=1;i<=v;i++)
			m[1][i]=w[1][i];
	for(i=2;i<=p;i++)
	{
		for(j=i;j<=v;j++)
		{
			m[i][j]=maxcost;
			for(int k=1;k<j;k++)
			{
				m[i][j]=min(m[i][j],m[i-1][k]+w[k+1][j]);
			}
		}
	}
	cout<<m[p][v]<<endl;
	return 0;
}