# Maximize The Cut Segments-dynamic programming

this sum is taken from geeksforgeeks

if you want to solve you can go to this link

Given an integer N denoting the Length of a line segment. you need to cut the line segment in such a way that the cut length of a line segment each time is integer either x , y or z. and after performing all cutting operation the total number of cutted segments must be maximum.

N=4

x,y,z=2 1 1

In first test case, total length is 4, and cut lengths are 2, 1 and 1. We can make maximum 4 segments each of length 1.

so

**output=>4**
N=5

x=5 ,y=3,z=2

we can make two segments of lengths 3 and 2.

**output=>2**

lets use dynamic programming to solve this question:

c++ implementation:

t is the no.of test cases:

**#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void mtcs(int a[],int length)
{
int dp[3][length+1];
int j=0;
for(int i=0;i<3;i++)
{
for(j=0;j<=length;j++)
{ if(j==0)
dp[i][j]=0;
else if(i==0)
{ if(j%a[i]==0)
dp[i][j]=j/a[i];
else
dp[i][j]=0;
}
else{
if(a[i]>j)
dp[i][j]=dp[i-1][j];
else
{
if(dp[i-1][j]==0 && dp[i][j-a[i]]==0 && j-a[i]!=0)
dp[i][j]=0;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-a[i]]+1);
}
}
}
}
cout<<dp[2][j-1];
}
int main() {
int t; cin>>t;
while(t--)
{ int length; cin>>length;
int a[3];
cin>>a[0]>>a[1]>>a[2];
sort(a,a+3);
mtcs(a,length);
cout<<endl;
}
return 0;
}
****
**