Cutted Segments

Cutted Segments

  October 08, 2017    

---

Problem :

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.

Idea is to Use DP

base case 0 as if length is 0 then 0 cut will be there.
find minimum of x,y,z and start loop from there .
Check if we have processed for i-minimum(x/y/)
and process 


Code:

public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
    int n=ab.nextInt();
    int x=ab.nextInt();
    int y=ab.nextInt();
    int z=ab.nextInt();
    int dp[]=new int[n+1];
    Arrays.fill(dp,1,n+1,-1);
    int start=Math.min(x,Math.min(y,z));
    for(int i=start;i<=n;++i)
    {
        if(i>=x && dp[i-x]!=-1)
        dp[i]=Math.max(dp[i],dp[i-x]+1);
        if(i>=y && dp[i-y]!=-1)
        dp[i]=Math.max(dp[i],dp[i-y]+1);
        if(i>=z && dp[i-z]!=-1)
        dp[i]=Math.max(dp[i],dp[i-z]+1);
    }
    System.out.println(dp[n]);
}