SPOJ

                        Forming Quiz Teams                                                       dp + bitmasking Problem Link   #include <iostream> #include <cstdio> #include <math.h> #include <cstring> #define sf(a) scanf("%d", &a) #define REP(i, n) for(int i = 0; i < n; i++) using namespace std; int n, posx, posy; char name[21]; double dist[17][17]; double dp[1 << 16]; int xy[17][2]; double solve(int bits) {     if(dp[bits] != -1)         return dp[bits];     if(bits == (1 << n) - 1)         return 0;     double ans = 1 << 30; // random big number     for(int i = 0; i < n; i++)     {         if(!(bits & (1 << i)))         {             for(int j = i + 1; j < n; j++)             {                 if(!(bits & (1 << j)))                 {                     ans = min(ans, solve(bits | (1 << i) | (1 << j)) +

                                      Jogging Trails                                                        bitwise DP  Problem Link #include <iostream> #include <cstring> #include <climits> #include <cstdio> #define INF INT_MAX #define sf(a) scanf("%d", &a) #define set(b, pos) ( b | (1 << pos) ) #define off(b, pos) ( b & ~( 1 << pos) ) #define test(b, pos) (b & (1 << pos) ) using namespace std; int v, e, st, en, wt, weight, bits; int graph[15][15]; int deg[15]; //stores degree of a node int memo[1 << 15]; int solve(int bits) {     if(memo[bits] >= 0)         return memo[bits];     int ans = INF;     int b;     for(int i = 0; i < v; i++)     {         for(int j = i + 1; j < v; j++)         {             if(test(bits, i) && test(bits, j))             {                 b = bits;                 b = off(b, i);            

                                 Twenty Questions                                                  DP + bitmasking Problem Link #include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; int F[128]; //feature set int dp[1 << 11][1 << 11]; //set of question and answer //denotes bitmask of question and answer int n, m; int solve(int Q, int A) {     if(dp[Q][A] != -1)         return dp[Q][A];     int nObjects = 0; //number of objects remaining after asking Q     for(int i = 0; i < n; i++)     {         if((F[i] & Q) == A)             nObjects++;     }     if(nObjects <= 1)     {         return dp[Q][A] = 0;     }     int nQuestions = m + 1;     //one by one ask each question and take the min number o question required to identify each object     for(int i = 0; i < m; i++)     {         if((Q & (1 << i)) == 0)

                                  Pebble Solitaire                                                 DP + bitmasking Problem Link #include <stdio.h> #include <string.h> #define min(a,b) a > b ? b: a void on( int &mask ,int pos){      mask |= ( 1 << pos) ; } void  off(int &mask,int pos){     mask = mask & ~( 1 << pos) ; } bool check( int mask , int pos ){      return bool( mask & ( 1 << pos) ) ; } int dp[ 1<<12 + 5 ] ; int solve( int mask) {     int &ret = dp[mask];     if( ret != -1 ) return ret;     ret = __builtin_popcount(mask);     for( int pos = 0 ; pos < 12 ; pos ++ )     {          if( pos < 10 && check(mask,pos) && check(mask,pos+1) && !check(mask,pos+2)){               int newmask = mask;               off(newmask,pos) , off( newmask , pos +1 ) , on(newmask,pos+2);               ret = min( ret , solve(newmask));          }