Exercise 8-12 of The Algorithm Design Manual. A certain string processing langua

Question

Exercise 8-12 of The Algorithm Design Manual. A certain string processing language allows the programmer to break a string into two pieces. It costs n units of time to break a string of n characters into two pieces, since this involves copying the old string. A programmer wants to break a string into many pieces, and 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 3, 8, and 10. If the breaks are made in left-right order, then the first break costs 20 units of time, the second break costs 17 units of time, and the third break costs 12 units of time, for a total of 49 steps. If the breaks are made in right-left order, 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, for a total of only 38 steps Give a dynamic programming algorithm that takes a list of character positions after which to break and determines the cheapest break cost in (n3) time. In your solution to this problem, it is suggested that you let S s1 S2 S, be the original string of length n, and let 0

Explanation / Answer

#include<iostream>
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<=m;i++)
scanf("%d",&a[i]);
m++;
a[m]=n;a[0]=0;
for(i=1;i<=m;i++)
{
for(j=i;j<=m;j++)
cost[i][j]=a[j]-a[i-1];
}
for(i=1;i<=m;i++)
f[i][i]=i;
memset(d,0,sizeof(d));
for(i=1;i<=m-1;i++)
{
for(j=1;i+j<=m;j++)
{
for(k=f[j][i+j-1];k<=f[j+1][i+j];k++)
{
if(!d[j][i+j]||d[j][i+j]>d[j][k]+d[k+1][i+j]+cost[j][i+j])
{
f[j][i+j]=k;
d[j][i+j]=d[j][k]+d[k+1][i+j]+cost[j][i+j];
}
}
}
}
printf("%d ",d[1][m]);
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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