Recusive Dp (Branch & Bound )

Strategy for the World Cup (codechef )


In this question we have to complete a given amount of runs using only 4's and 6's
 we have to say the no. of ways by which we can do this.


 in this question there are four cases
 case 1) run=6    then--->> ball= ball-1 , run=run-6, wicket=wicket
 case 2) run=4     then--->> ball= ball-1 , run=run-4, wicket=wicket
 case 3) run=0     then--->> ball= ball-1 , run=run, wicket=wicket
 case 4) run=out  then--->> ball= ball-1 , run=run, wicket=wicket-1


base case if (run==0 && bal==0 && w>=0 ) this will return 1;







#include<bits/stdc++.h>

using namespace std;

long long  dp[305][1805][15];

long long  solve(long long  b,long long  r,long long  w)
{
  long long  a=0;

  if(r==0 && b==0 && w>=0)
  return 1;

  if(w<0 || b<=0 || r<0)
  return 0;

 if(dp[b][r][w]!=-1)
  {
    return dp[b][r][w];
  }
 
 
 long long  &ret=dp[b][r][w];
   ret=0;


   a=a+solve(b-1,r-6,w);
   a=a%1000000007;

   a=a+solve(b-1,r-4,w);
   a=a%1000000007;

   a=a+solve(b-1,r,w);
   a=a%1000000007;

   a=a+solve(b-1,r,w-1);
   a=a%1000000007;
   return ret=a;

}




int  main()
{
 long long i,j,k;
 //memset(dp,-1,sizeof(dp));
 for(i=0;i<301;i++)
     for(j=0;j<1801;j++)
       for(k=0;k<11;k++)
         dp[i][j][k]=-1;
 long long  t;
 cin>>t;
 while(t--)
 {
  long long  b,r,w,i;
  cin>>r>>b>>w;

  if(r>1800 || r%2==1 )
    cout<<0<<endl;
  else
  cout<<solve(b,r,w)<<endl;
 }
return 0;
}

Comments

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.