Nastya and Scoreboard

发表于 更新于 分类于 ，

    给出n个7极管的发光情况（用7位二进制表示）。

    现在恰好额外点亮k个灭了的管，问能组成的最大数是多少。如果不能组成合法的数字则输出-1

Nastya and Scoreboard

Created by LXC on Tue Jun 6 00:42:06 2023

https://codeforces.com/problemset/problem/1340/B

ranting: 1700

tag: bitmasks, dp, graphs, greedy

problem

给出n个7极管的发光情况（用7位二进制表示）。

现在恰好额外点亮k个灭了的管，问能组成的最大数是多少。如果不能组成合法的数字则输出-1

solution

动态规划。类似01背包

我们先预处理出每个管i能变成的数字u以及需要代价v。

定义$f_{i,j}$为从第i到第n-1个7极管在恰好点亮j个灭了的管后，在能够组成的最大字典序的情况下第i个数的值。

可以初始化$f_{n,0} \ne INF$,其余均为$INF$
状态转移$f_{i,j} = \max \limits_{f_{i+1, j-v_i} \ne INF} u_i$，第i个管变为数字$u_i$需要的代价是$v_i$

答案的序列就是$f_{0,k}, f_{1, k-f_{0,k}}, f_{2, k-f_{1,k-f_{0,k}}},\cdots$

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;

int d[10];
int bitcnt(int x) {
    int rt = 0;
    for (; x; x = x & (x - 1))
        rt++;
    return rt;
}
int to_dec(string& s) {
    int rt = 0;
    for (int j = 0; j < 7; j++) {
        if (s[j] == '1')
            rt |= 1 << j;
    }
    return rt;
}

void sol() {
    int n, k;
    cin >> n >> k;
    vector<vector<pair<int, int>>> a(n);  // 可变数字，需要点亮数
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int x = to_dec(s);
        for (int j = 0; j < 10; j++) {
            if ((x ^ d[j]) == d[j] - x) {  // d[j] 包含 x
                a[i].emplace_back(j, bitcnt(d[j] - x));
            }
        }
        // for (auto& [i, j] : a[i]) {
        //     cout << "[" << i << " " << j << "]"
        //          << " ";
        // }
        // cout << endl;
    }
    // dp[i][j]
    // 后i个数在恰好用了j次点亮后的能形成最大字典序，且第i个数是dp[i][j]
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, INF));
    dp[n][0] = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            for (auto [u, v] : a[i]) {
                if (j - v >= 0 && dp[i + 1][j - v] != INF)
                    dp[i][j] = u;
            }
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j <= k; j++) {
    //         cout << i << " " << j << " " << dp[i][j] << endl;
    //     }
    // }
    vector<int> ans;
    int i = 0, j = k;
    while (i < n && j >= 0 && dp[i][j] != INF) {
        ans.push_back(dp[i][j]);
        for (auto [u, v] : a[i]) {
            if (u == dp[i][j]) {
                j -= v;
                i++;
                break;
            }
        }
    }
    if (ans.size() == 0) {
        cout << "-1\n";
        return;
    }
    for (int i : ans) {
        cout << i;
    }
    cout << endl;
}

int main() {
    vector<string> num = {"1110111", "0010010", "1011101", "1011011",
                          "0111010", "1101011", "1101111", "1010010",
                          "1111111", "1111011"};
    for (int i = 0; i < 10; i++) {
        d[i] = to_dec(num[i]);
        // cout << d[i] << " ";
    }
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}