**Problem:**

Please find the problem here.

**Solution:**

First notice this problem is an 'ordering' problem. We are trying to find an order. To determine an order you make a choice which one is the first one to go, and then which is next, and so on.

A little fiddling make me realize the sub-problems are overlapped. It doesn't matter how I get to the state of cutting a stick from the m

^{th}endpoint to the n

^{th}endpoint, I just have to solve that sub-problem optimally.

So in the view of this, we define the recurrence relation as follow

Let opt(m, n) be the minimal cost of cutting the stick from the m

^{th}endpoint to the n

^{th}endpoint.

Base case, we have opt(m, m+1) = 0, because there is no need to cut a segment with no internal endpoints.

Inductively, we have opt(m, n) = endpoints(n) - endpoint(m) + min over k (opt(m, k) + opt(k, n)). We have to make a cut anyway and that will always cost us endpoints(n) - endpoint(m) independent on where we choose, and we need to choose one, that minimize subsequent costs.

That's it, given the recurrence formula we can code up the bottom up DP easily.

**Code:**

#include "stdafx.h" // http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944 #include "UVa10003.h" #include <iostream> #include <vector> using namespace std; int UVa10003() { while (true) { int stick_length; int num_cuts; cin >> stick_length; if (stick_length == 0) { break; } cin >> num_cuts; vector<int> endpoints; endpoints.resize(num_cuts + 2); endpoints[0] = 0; for (int i = 1; i <= num_cuts; i++) { int cut; cin >> cut; endpoints[i] = cut; } endpoints[num_cuts + 1] = stick_length; vector<vector<int> > opt; opt.resize(endpoints.size()); for (unsigned int i = 0; i < endpoints.size(); i++) { opt[i].resize(endpoints.size()); } // Initialization - minimal cost of cutting a segment with no cutting point in it is 0 for (unsigned int i = 0; i < endpoints.size() - 1; i++) { opt[i][i + 1] = 0; } for (unsigned int gap = 2; gap <= endpoints.size() - 1; gap++) { for (unsigned int i = 0; i + gap < endpoints.size(); i++) { int j = i + gap; int segment_length = endpoints[j] - endpoints[i]; bool first = true; int min = -1; for (int k = i + 1; k < j; k++) { int cost = opt[i][k] + opt[k][j];; if (first) { min = cost; first = false; } else { if (cost < min) { min = cost; } } } opt[i][j] = segment_length + min; } } cout << "The minimum cutting is " << opt[0][endpoints.size() - 1] << "." << endl; } return 0; }

Thanks a lot. This post was really helpful.

ReplyDeleteThanks a lot. This post was really helpful.

ReplyDeletevery nice explanation! saved me a lot of time!

ReplyDelete