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;↵
↵
int exp( int bs, int po)↵
{↵
int ans = 1 ;↵
while(po)↵
{↵
if(po&1) ans*=bs;↵
bs*=bs;↵
po>>=1;↵
}↵
return ans;↵
}↵
↵
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;↵
}↵
↵
~~~~~↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long ll;↵
↵
{↵
int ans = 1 ;↵
while(po)↵
{↵
if(po&1) ans*=bs;↵
bs*=bs;↵
po>>=1;↵
}↵
return ans;↵
}↵
↵
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)↵
↵
↵
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;↵
}↵
↵
~~~~~↵
↵
