An Easy DP Problem-2 with Bitmask

Given N integers. Let Total subsets T=2^N. 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;
}

About Alim

ACM Competitive Programmer

‹ Project Euler 16

SRM-613(Div-2) 1000 ›

Posted in Dynamic Programming