anwer link-“http://ideone.com/e.js/5jUAHu” type=“text/javascript”
problem link-SPOJ.com - Problem LINEUP
using (dp+bitmask) getting WA
in masking i am using set of positions
anwer link-“http://ideone.com/e.js/5jUAHu” type=“text/javascript”
problem link-SPOJ.com - Problem LINEUP
using (dp+bitmask) getting WA
in masking i am using set of positions
My code
#include<stdio.h>
#include<climits>
#include<algorithm>
using namespace std;
int DP[1<<11];
int main()
{
int T;
scanf("%d",&T);
for(;T;--T)
{
int N=11,i,j,k;
int A[12][12];
for(i=1;i<=11;i++)
for(j=1;j<=11;j++)
scanf("%d",&A[i][j]);
/*
SO again there are 11 positions and 11 players
Each one should get one which kinds of maximises
the answer
Let DP[i][MAsk] be the optimal solution to i and mask subset
Now we dont need i again masks tell us that
So what are we up to ?? One more older simple problem
*/
DP[0]=0;//The cost of Phi
for(i=1;i<(1<<11);i++)
{
DP[i]=INT_MIN;
int ctr=__builtin_popcount(i);
for(j=1;j<=11;j++)
{
if( (i&(1<<(j-1))) && A[ctr][j] )
DP[i]=max(DP[i],DP[i^(1<<(j-1))]+A[ctr][j]);
}
}
printf("%d\n",DP[(1<<11)-1]);
}
return 0;
}