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++)   ...

                                      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 ...

                                 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)            ...

                                  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 ++ )   ...