poj 1160 동태 기획(1차원 도시 우체국 건설)

#include <stdio.h>
#include <string.h>
#define N 303
int n,m;
int dp[N][N],dis[N][N],s[N];
int min(int a,int b){
	if(a<b)
		return a;
	return b;
}
int main(){
	freopen("a.txt","r",stdin);
	while(scanf("%d %d",&n,&m)!=EOF){
		int i,j,k;
		memset(dis,0,sizeof(dis));
		for(i = 0;i<=n;i++)
			for(j = 0;j<=n;j++)
				dp[i][j] = 0x3fffffff;
		for(i = 1;i<=n;i++)
			scanf("%d",&s[i]);
		for(k = 1;k<n;k++)//  dis  
			for(i = 1;i+k<=n;i++){
				dis[i][i+k] = s[i+k]-s[i];
				for(j = 1;i+j<i+k-j;j++)
					dis[i][i+k] += s[i+k-j] - s[i+j];
			}
		for(i = 1;i<=n;i++)
			dp[i][1] = dis[1][i];
		for(i = 1;i<=n;i++)
			for(j = 2;j<=i&&j<=m;j++)
				for(k = j-1;k<i;k++)
					dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);
		printf("%d
",dp[n][m]);
	}
	return 0;
}