T1. 组队
考虑状压 DP。复杂度 \(O(2^n\times n^3)\)。实际上严重跑不满因为你只需要考虑 \(1\) 的个数为 \(3\) 的倍数的状态。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i ++ )
#define DF(i, a, b) for (int i = (a); i >= (b); i -- )
inline void chkmin(int& a, int b) { if (a > b) a = b; }
inline void chkmax(int& a, int b) { if (a < b) a = b; }const int N = 25;vector<int> v[N];
int n;
int val[N][N];
int a[N], t[N][N][N];
int dp[1 << 22];signed main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;F(i, 1, n) cin >> a[i];F(i, 1, n) F(j, 1, n) cin >> val[i][j];F(i, 0, (1 << n) - 1) v[__builtin_popcount(i)].push_back(i);F(i, 1, n) F(j, i + 1, n) F(k, j + 1, n)t[i][j][k] = max({a[i], a[j], a[k], val[i][j], val[j][k], val[i][k], val[i][j] * val[j][k] * val[i][k]});memset(dp, -0x3f, sizeof dp);dp[0] = 0;for (int i = 0; i < n; i += 3)for (auto j : v[i]) F(a, 0, n - 1)if (!(j >> a & 1))F(b, a + 1, n - 1)if ((!(j >> b & 1)))F(c, b + 1, n - 1)if (!(j >> c & 1))chkmax(dp[j ^ (1 << a) ^ (1 << b) ^ (1 << c)], dp[j] + t[a + 1][b + 1][c + 1]);cout << dp[(1 << n) - 1] << "\n";return 0;
}T2. 幸运数字
考虑 \(\times 21\) 相当于 \(\times 16+\times 4+\times 1\)，而乘上 \(2\) 的整数次幂等价于在后面增加 \(0\)。所以实际上只需实现二进制加法即可。