An Easy DP Problem-2 with Bitmask

Given N integers. Let Total subsets T=2N. How many subsets are available from T where the distinct integers are less than or equal to K.

Sample Input:

4 2 (N,K)

1 2 3 4(A[i])

Sample Output:

11

Sample Input:

4 2 (N,K)

5 5 5 5(A[i])

Sample Output:

16

Related Problem

Solution:

#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL dp[59][1055];
LL a[59],n,k;

LL f(LL i,LL mask)
{
    if(dp[i][mask]!=-1) return dp[i][mask];
    if(i==n)
    {
        LL p=__builtin_popcount(mask);
        if(p<=k) return 1;
        else return 0;
    }
    LL res=f(i+1,mask); //not using i-th integer
    LL nmask=mask;
    nmask=nmask|(1<<a[i]);
    res=res+f(i+1,nmask); //using i-th integer
    return dp[i][mask]=res;
}


int main()
{
    LL i,j,m,d;
    while(cin>>n>>k)
    {
        memset(dp,-1,sizeof(dp));
        for(i=0;i<n;i++)
            cin>>a[i];
        LL ans=f(0,0);
        cout<<ans<<endl;
    }
    return 0;
}

Advertisements
About

ACM Competitive Programmer

Posted in Dynamic Programming
2 comments on “An Easy DP Problem-2 with Bitmask
  1. Anonymous says:

    how this is 11 ??

  2. Larry Page says:

    size should be <= k.
    so {},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4} = 11.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: