UVa-10003 : Cutting Sticks

問題概要

長さL(<1000)の木をN(<50)箇所で切る。切るには今つながってる部分の長さだけコストがかかる。切る順番をうまく選ぶことによってコストを最小化する問題。

解法

[from, to)型のメモ化再帰。ひとつの状態から、どこを切るかを全部試す。

acceptされたコード

計算量O(N^3)。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 50;
const int INF = 1<<29;

int L, N;
int cuts[MAX_N+2];
bool visited[MAX_N+2][MAX_N+2];
int memo[MAX_N+2][MAX_N+2];

void init(){
	scanf("%d", &N);

	for(int i=0; i<N; i++){
		scanf("%d", cuts+i+1);
	}
	cuts[N+1] = L;

	memset(visited, false, sizeof(visited));
}

//[from, to)
int rec(int from, int to){
	//メモ化処理
	if(visited[from][to]){
		return memo[from][to];
	}
	visited[from][to] = true;

	int& ret = memo[from][to];
	ret = INF;

	//基底
	if(to - from == 1){
		return ret = 0;
	}

	for(int mid=from+1; mid < to; mid++){
		ret = min(ret, cuts[to] - cuts[from] + rec(from, mid) + rec(mid, to));
	}
	return ret;
}

int solve(){
	return rec(0, N+1);
}

int main(){
	while(scanf("%d", &L), L){
		init();
		printf("The minimum cutting is %d.\n", solve());
	}

	return 0;
}