A certain string-processing language allows a programmer to break a string into

Question

A certain string-processing language allows a
programmer to break a string into two pieces. Because this operation copies
the string, it costs n time units to break a string of n characters into two
pieces. Suppose a programmer wants to break a string into many pieces. The
order in which the breaks occur can affect the total amount of time used.
For example, suppose that the programmer wants to break a 20-character
string after characters 2, 8, and 10 (numbering the characters in ascending
order from the left-hand end, starting from 1). If she programs the breaks
to occur in left-to-right order, then the first break costs 20 time units, the
second break costs 18 time units and the third break costs 12 time units,
totaling 50 time units. If she programs the breaks to occur in right-to-left
order, however, then the first break costs 20 time units, the second break
costs 10 time units, and the third break costs 8 time units, totaling 38 time
units. In yet another order, she could break first at 8 (costing 20), then break
the left piece at 2 (costing 8), and finally the right piece at 10 (costing 12),
for a total cost of 40.
Design an algorithm that, given the numbers of characters after which
to break, determines a least-cost way to sequence those breaks. More formally,
given a string S with n characters and an array L[1..m] containing the break points, compute the lowest cost for a sequence of breaks, along with a
sequence of breaks that achieves this cost.

Explanation / Answer

The code isn't proper here. So I pasted it here http://pastebin.com/EfYe1D7a There you can see it proper syntax highlighting and indentation. Please rate :) #include using namespace std; int d[1010][1010],f[1010][1010]; int cost[1010][1010]; int main() { int i,j,k,n,m,a[1010]; while(scanf("%d %d",&n,&m)!=EOF) { for(i=1;i

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.