2020百度之星 1004-Car(二分，二进制枚举子集)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6778
解题思路：
二分答案，用f[i][j]表示存不存在到了第i天，二进制表示为j的尾号组(对于某一个尾号，被限制为1，不被限制为0)已经被限制过的情况；对于第i+1天，枚举剩下尾号的子集，判断可行不可行，即可进行转移。

#include<bits/stdc++.h>
using namespace std;
char s[10];
int c[10];
bool f[10][1<<10];
bool judge(int k, int s)
{
    for(int i = 0; i <= 9; i++) if((k>>i) & 1) s-=c[i];
    return s <= 0;
}
bool check(int mid)
{
    int s = 0; for(int i = 0; i <= 9; i++) s+=c[i];
    s -= mid;
    memset(f, 0, sizeof(f));
    for(int i = 0; i < (1<<10); i++) if(judge(i,s)) f[0][i] = 1;
    for(int i = 1; i <5; i++)
    {
        for(int j = 0; j < (1<<10); j++)    //枚举集合 
        {
            for(int k = j, l; k; k = (k-1)&j)    //枚举子集 
            {
                l = j^k;
                if(!f[i-1][l] || !judge(k,s)) continue;
                f[i][j] = 1;
                break;
            }
        }
    }
    for(int i = 0; i < (1 << 10); i++) if(f[4][i]) return 1;
    return 0;
}
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) {
            scanf("%s",s);
            c[s[4]-'0']++;
        }
        printf("%d\n",bsearch_1(1, n) );
    }
}