A certain string-processing language allows the programmer to break a string int

Question

A certain string-processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time 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 are made can affect the total amount of time used.
For example, suppose we wish 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 the breaks are made in left-to-right order, then the first break cost 20 units of time, the second break costs 18 units of time, and the third breaks costs 12 units of time, a total of 50 units of time.
If the breaks are made in right-to-left order, then the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of 38 units of time.
Design an algorithm give breaking points and string length, determine least cost way to sequence those breaks.

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.