ZOJ 1196 Fast Foodダイナミック企画

テーマリンク: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1196
想定状態p(n,k)はn店舗前にk個の倉庫を建てる最適距離を表します.
p(n,k)=min(p(i,k-1)+mindis(i+1,n) 
//その中のk-1<=j==i-1,dis[i][j]はi番目のホテルからj番目のホテルまで供給点を追加して達成した最小値を表しています.i,jの中間値を取ればいいです.
つまり、0からiの間にk-1の供給ステーションを建設することを求めます.iを加えて、nの間に供給ステーションの最小値を建設します.0からiは父の問題になりました.
for iを押して最小の値をください.
dis[i][j]はi,jの間に供給ステーションを建設し、i,jの間に建てられたホテルの中で、すなわち第(i＋j)/2軒のホテルのうち、i,jの間に各ホテルはこの供給ステーションに行きます. 
この倉庫までの距離と;店iの前のk-1の倉庫が最適な位置に建っているなら、次の最適な席にしたいです.
置は確かにi＋1から終点の間に建てられています.そしてm店の前には最大でm個の倉庫しか建てられません.だからiの範囲は確定できます.

#include "iostream"
#include "cstdlib"
using namespace std;

int data[220];				//         
int mindis[220][220];		//   i, j         ， i, j            
int result[220][40];		//      
int n, k;

int searchResult(int n, int k){
	if(n <= k)    //n < k         999999，       0         ，                 
		return 0;
	if(k == 1)
		return mindis[1][n];
	if(result[n][k] != -1)		//        n    k    ，         
		return result[n][k];
	int min = 999999999;
	int i;
	for(i = k - 1; i < n; i++){
		int temp = searchResult(i, k - 1) + mindis[i + 1][n];
		if(temp < min)		
			min = temp;
	}
	result[n][k] = min;
	return min;
}

int main(){
	int iCase=0;
	while(cin >> n >> k && n && k){
		int i, j;
		for(i = 1; i <= n; i++){
			cin >> data[i];
			for(j = 0; j <= n; j++)
				result[i][j] = -1;		//   
		}
		int mid;
		for(i = 1; i <= n; i++){
			mindis[i][i] = 0;
			for(j = i + 1; j <= n; j++){
				int p;
				mindis[i][j] = 0;
				mid = (i + j) / 2;
				for(p = i; p <= j; p++)
					mindis[i][j] += abs(data[p] - data[mid]);
			}				
		}
		cout<<"Chain " << ++iCase << endl;
		cout<<"Total distance sum = "<< searchResult(n , k ) << endl << endl; 
	}
	return 0;
}