Moovie Mooving题解状压DP

这题如果一看我们首先会想贪心，但是之后我们却不能找到一个合适的时间去替换，如何再看完时间的条件下，找到最少的电影次数，那么贪心不行那就只有想想DP了，这题就是用状压来过，所谓状压其实就是以二进制来处理各种位置的关系
这是雨状压有关的二进制的处理。
言归正传。
dp[k]代表什么呢 就是k在二进制下，有多少个1就可以看多少个电影，那么dp[k]就是看的时间长度，我们每次处理的时间更新是dp[k]=max(dp[k],ans[j][pos]+d[j]);
然后就是一个很6的操作，如何快速找K的1的个数

int solve(int x)
{
int cnt=0;
while(x)
{
  cnt++;
  x-=x&-x;
// x&-x在树状数组里面是不是找最下面的一个1，就是最低位的1，我们每次都减去最低位是不是就可以顺利统计啦
return cnt；

}
}

是不是有人说这个代码太多了 有没有简洁啊，当然有啦，
使用这个函数 ————builtin_popcount(k);
直接返回二进制下1的个数

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
vector<int>ans[33];
int dp[1<<21];
int main()
{
    fio;
    int n,l;
    cin>>n>>l;
    int d[30],c;
    for(int i=0; i<n; i++)
    {
        cin>>d[i]>>c;
        for(int j=0; j<c; j++)
        {
            int x;
            cin>>x;
            ans[i].push_back(x);
        }
    }
    int an=33;
    mse(dp,0);
    for(int i=1; i<1<<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i>>j&1)
            {
                int dou=i^(1<<j);
                int pos=upper_bound(ans[j].begin(),ans[j].end(),dp[dou])-ans[j].begin()-1;
               // cout<<pos<<endl;
                if(pos>=0)
                    dp[i]=max(dp[i],ans[j][pos]+d[j]);
            }
        }

    }
    for(int i=1;i<1<<n;i++)
        if(dp[i]>=l)
        an=min(an,__builtin_popcount(i));
    if(an==33)
        cout<<-1<<endl;
    else
        cout<<an<<endl;
    return 0;

}