标签：cnt false int MagicMolecule perm 55 fl

剪枝 #Topcoder

考虑爆搜，给这个加上最优性和可行性剪枝

具体来说，可行性判 \(3\times (cnt+possible)\geq 2n\)

最优性可以记录每个状态是否合法，对于有合法后继的，记录最大的 \(cur\)，否则记录最多选几个数

// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

ull fl, bt[55];
int n;
int val[55];
char s[55];
int res = 0;
bool flag = false;
unordered_map<ull, int> mp[55], mi[55];
int perm[55];

bool dfs(int curx, int ans, int cnt)
{
    // debug(x, ans, cnt, mp[x][fl]);
    // random_shuffle(perm + curx, perm + 1 + n);
    if (cnt * 3 >= 2 * n)
    {
        res = max(res, ans);
        flag = true;
    }
    // if ((double)clock() / CLOCKS_PER_SEC * 1000.0 >= 800)
    // {
    //     cout << res << endl;
    //     exit(0);
    // }
    if (curx > n)
    {
        if (cnt * 3 >= n * 2)
            return true;
        return false;
    }
    int x = perm[curx];
    if ((cnt + __builtin_popcountll(fl)) * 3 < 2 * n)
        return false;
    if (mp[x].count(fl) && mp[x][fl] > ans)
        return false;
    if (mi[x].count(fl) && mi[x][fl] > cnt)
        return false;
    // debug(x, ans, cnt);
    bool flg = false;
    ull tmp = fl;
    if (fl & (1ull << x))
    {
        fl &= bt[x];
        flg |= dfs(curx + 1, ans + val[x], cnt + 1);
        fl = tmp;
        fl ^= (1ull << x);
        flg |= dfs(curx + 1, ans, cnt);
        fl = tmp;
    }
    else
    {
        flg |= dfs(curx + 1, ans, cnt);
        fl = tmp;
    }
    if (flg)
        mp[x][fl] = ans;
    else
        mi[x][fl] = max(mi[x][fl], cnt - 1);
    return flg;
}

void solve()
{
    // srand(time(0));
    cin >> n;
    rep(i, 1, n)
    {
        cin >> val[i];
        perm[i] = i;
    }
    debug(perm);
    cin >> n;
    rep(i, 1, n)
    {
        cin >> (s + 1);
        rep(j, 1, n)
        {
            if (s[j] == 'Y')
            {
                // debug(i, j);
                bt[i] |= (1ull << j);
            }
        }
    }
    // random_shuffle(perm + 1, perm + 1 + n);
    fl = (1ull << (n + 1)) - 1;
    fl ^= 1;
    dfs(1, 0, 0);
    if (!flag)
    {
        cout << "-1" << endl;
        return;
    }
    cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}

很好的 \(20\) 发提交，让我的脑子旋转~~~

标签：cnt,false,int,MagicMolecule,perm,55,fl
From： https://www.cnblogs.com/xiaruize/p/18136776