https://www.spoj.pl/problems/LISA/
this problem is similar to what you have mentioned. I have attached my dp
solution to this problem.
The lines of the algo is similar to matrix chain multiplication.
>
>
>
Regards,
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#include<iostream>
#include<cstring>
#include<climits>
using namespace std;
struct res
{
int max,min;
}m[101][101];
main()
{
int i,t,l,j,length,q,q1,k;
char str[200];
cin>>t;
while(t--)
{
cin>>str;
length=strlen(str);
for(i=0;i<=length-1;i++)
m[i][i].max=m[i][i].min=str[i]-48;
for(i=0;i<=length-3;i++)
{
if(str[i+1]=='+')
m[i][i+2].max=m[i][i+2].min=str[i]+str[i+2]-96;
else
m[i][i+2].max=m[i][i+2].min=(str[i]-48)*(str[i+2]-48);
}
for(l=4;l<length;l+=2)
{
for(i=0;i<=length-l-1;i++)
{
j=i+l;
m[i][j].max=INT_MIN;
m[i][j].min=INT_MAX;
for(k=i;k<=j-2;k+=2)
{
if(str[k+1]=='+')
{
q=m[i][k].max+m[k+2][j].max;
q1=m[i][k].min+m[k+2][j].min;
}
else
{
q=m[i][k].max*m[k+2][j].max;
q1=m[i][k].min*m[k+2][j].min;
}
m[i][j].max=std::max(m[i][j].max,q);
m[i][j].min=std::min(m[i][j].min,q1);
}
}
}
cout<<m[0][length-1].max<<" "<<m[0][length-1].min<<endl;
}
}
