HDU 1951 Vase collection(DFS)

Vase collection

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long LL;
LL state[40];//记录每种形状出现多少种装饰

int ans;

int check(LL cnt) {
    int t = 0;
    for(; cnt; cnt >>= 1)
        t += (cnt&1);//记录cnt中多少位为1，即两种形状有多少个相同的装饰
    return t;
}

void dfs(int now, int cur, LL cnt) {//第cur个vase cnt匹配的状态
    /*
    if(ans < now)
        ans = now;

    for(; cur <= 36; cur++) {
        if(check(cnt & state[cur]) >= now + 1)
            dfs(now+1, cur+1, cnt & state[cur]);
    }
    */
    if(cur > 36) {//全部整完了
        ans = max(ans, now);
        return;
    }

    if(check(cnt & state[cur]) >= now + 1)//这个可以匹配且结果更优,那就整哈
        dfs(now+1, cur+1, cnt & state[cur]);

    dfs(now, cur+1, cnt);//这个不整(其实就是且结果更优但不整， 压根就不匹配2种情况)
}

int main() {
    //freopen("data.in", "r", stdin);
    int t, n, a, b;
    scanf("%d",&t);

    while(t--) {
        ans=0;
        memset(state, 0, sizeof(state));
        scanf("%d",&n);
        for(int i = 0; i < n; i++) {
            scanf("%d %d",&a, &b);//a是瓶子，b是装饰风格
            state[a] |= (1LL << b);//用位或运算可以记录每种形状出现装饰的次数
        }

        //cout << ((1LL << 36) -1 )<< endl;
        dfs(0, 1, (1LL << 36)-1);state的值>=2 从1号瓶子开始搜索,全1

        printf("%d\n", ans);
    }
    return 0;
}