dp / bit-masking / dp with profile / matrix multiplicexponentiation
Difference between en2 and en3, changed 2,314 character(s)
I am trying to solve  http://www.spoj.com/problems/AIRLINES/ using DP , for which i  wrote a solution using 3-D dp, but its too slow , if  anyone could  suggest me improvements and appropriate logic  it would be very helpful , here is the ideone link http://ideone.com/QKspPN↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

typedef long long ll;↵

ll m , n ,  k ;↵
int dp[32800][51][51];↵

ll rec(int vtx , vector<vector<int> > &g,ll sum ,ll idx,vector<int>&ct)↵
 {↵
   ll tp = 0;↵

      if(sum > k || idx > n)↵
        return 0 ;↵

     if( idx == n && sum == k )↵
          tp = 1 ;↵

      if(dp[vtx][sum][idx]!=-1)↵
         return dp[vtx][sum][idx];↵

     for( size_t i = 0 ; i<g[vtx].size() ; i ++ )↵
        {↵
             int vt = g[vtx][i] ;↵
             tp += rec( vt , g , sum + ct[ vt ] , idx + 1 ,ct);↵
        }↵

     dp[vtx][sum][idx]  = tp;↵
          return tp;↵
 }↵

int main()↵

{↵
  ios::sync_with_stdio(0);↵
  cin.tie(0);↵

  cin>>m>>n>>k;↵

  vector<int>vst; // To store valid states↵
  vector<vector<int> > g(32800); // to store paths form one valid state to another↵
  vector<int>ct(32800); // to store number of 1s in ach valid state  ↵

  //vector<int>idx(32800);↵

// finding the valid states ↵
  for( int i =  0 ; i < exp(2,m) ; i ++ )↵
    for( int j = 1; j <32 ; j ++ )↵
      {↵
           if( (1<<j)&i  && (1<<(j-1))&i )↵
               break;↵

           if(j==31)↵
             vst.push_back(i);↵
      }↵


// finding the paths ↵
   for( size_t i =0 ; i < vst.size() ; i ++ )↵
     for( size_t j = 0 ; j <  vst.size() ; j ++ )↵
         for( size_t  k = 0 ; k < 32 ; k ++  )↵
              {↵
                if( 1<<k & vst[i]  &&  1<<k & vst[j])↵
                       break;↵

                  if(k==31)g[vst[i]].push_back(vst[j]);↵
               }↵


// finding the number of 1s in  a valid state ↵

       for( size_t i = 0 ; i < vst.size() ; i++ )↵
            { int tp = 0 ;↵
               for( int j = 0 ; j < 32 ; j++ )↵
                   if(1<<j & vst[i])↵
                       tp++;↵

               ct[vst[i]] = tp ;↵
            }↵


       ll sum = 0 ;↵

      memset(dp,-1,sizeof(dp));↵
       for( size_t i = 0 ; i < vst.size() ; i ++ )↵
           sum+= rec(vst[i],g, ct[vst[i]] ,1,ct);↵

      cout<< sum<<endl;↵
}↵

~~~~~↵

 
How to approach this problem  http://www.spoj.com/problems/AIRLINES/ 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English saisumit 2016-02-09 06:43:19 2314
en2 English saisumit 2016-02-08 21:22:47 233
en1 English saisumit 2016-02-08 21:20:33 2502 Initial revision (published)