Ta gọi ~dp(i, mask)~ là đáp án nếu xét ~i~ số nguyên đầu và các chữ số đã được chọn là bit ~1~ thuộc ~mask~. Giả sử số ~i + 1~ có những chữ số thuộc ~state~. Nếu ~mask~ và ~state~ không có bit ~1~ chung thì ta có thể cập nhật đáp án:

~dp(i + 1, mask | state) = max(dp(i + 1, mask | state), dp(i, mask) + a(i + 1))~.

Đây là kĩ thuật thường được gọi dp bitmask.

Code mẫu

// TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"

using namespace std;
typedef long long ll;
const int N = 1010;

int n;
ll a[N], dp[N][(1<<10)+1];

void solve() {
    int t;
    cin >> t;
    while(t--) {
        memset(dp, 0, sizeof(dp));
        cin >> n;
        for(int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        for(int i = 1; i <= n; ++i) {
            int curMask = 0;
            ll tmp = a[i];
            do {
                int c = (tmp % 10);
                if(BIT(curMask, c)) {
                    curMask = -1;
                    break;
                }
                curMask |= (1 << c);
                tmp /= 10;
            } while(tmp > 0);

            for(int mask = 0; mask < (1<<10); ++mask) {
                dp[i][mask] = max(dp[i][mask], dp[i-1][mask]);
                if(curMask != -1 && !(mask & curMask)) {
                    dp[i][mask | curMask] = max(dp[i][mask|curMask], dp[i-1][mask] + a[i]);
                }
            }
        }
        ll res = 0;
        for(int mask = 0; mask < (1<<10); ++mask) {
            res = max(res, dp[n][mask]);
        }
        cout << res << '\n';   
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
#endif // ONLINE_JUDGE
    solve();
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}