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; }