vector<vector<int> > cuts(int n, vector<int> A)
{
int min;
int numcuts = A.size();
vector<vector<int> > Cuts(vector<int> V(0,n), n);
vector<vector<int> > Result(vector<int> V(0,n), n);
for(int i=0;i<numcuts;i++)
{
Cuts[A[i]][A[i]]=0;
Cuts[A[i]][A[i+1]]=0;
}
for(int cutlen=2;cutlen<numcuts;cutlen++)
for(int i=0;i<(numcuts-cutlen);i++)
{
min=INT_MAX;
for (k = i + 1; k < (i + cutlen); ++k)
{
if(min < (Cuts[A[i]][A[k]] + Cuts[A[k]][A[i+cutlen]]))
Result[A[i]][A[i+cutlen]]=k;
}
Cuts[i][i+len] = min + A[i + len] - A[i];
}
return Result;
}
On Tue, Feb 1, 2011 at 11:47 AM, ritu <[email protected]> wrote:
> sorry ..the complete question is
>
>
> You are given a wooden log of length n. It has n+1 grooves marked on
> it from 0 to n. You are given an array containing numbers within the
> range of 1 to n-1. These elements of the array represents the points
> on the log at which u need to cut the wooden log. Now the cost of
> cutting a log is proportional to the length of the original log being
> cut.
> Eg: n=15 and A={1,5,9}
> Now when u make a cut at 1, the cost is n (the size of original log)
> When u cut at 9, the cost will be n-1 as the length of the new
> original log is 1 to n i.e n-1
> When u cut at 5, since 5 lies between 1 and 9 and the length of this
> log is 9-1=8, so the cost will be 8.
>
>
> The question is: given the value of 'n' and the Array A containing the
> points at which u need to make a cut, find the order in which the cuts
> must be made in order to minimize the total cost of cutting the wooden
> log.
>
> --
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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.
