思路
求出每位数字表示0~9所需的棍子数（相当于代价）。这样就可以用背包dp来找出恰好有k个棍子下的解。
dp[i][k] 代表 已经确定了i位的数字后，当前还剩k个棍子的状态可取到的最大数字(最大0~9)。
#include <bits/stdc++.h>
using namespace std;
const int N = 4e3;
vector<string> sdigital{ "1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
vector<bitset<7>> digital;
typedef pair<int, int> PII;
int dp[N][N];
int lastk[N][N];
vector<PII> num[N];
int main() {
ios::sync_with_stdio(false);
for(auto s : sdigital) {
digital.push_back(bitset<7>(s));
}
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i++) {
string s;
cin >> s;
bitset<7> bs(s);
for(int j = 0; j < digital.size(); j++) {
auto &di = digital[j];
if((di & bs) != bs) continue;
num[i].push_back(make_pair(di.count() - bs.count(), j + 1));
}
}
for(auto v : num[n]) {
dp[n][v.first] = max(dp[n][v.first], v.second);
}
for(int i = n -1; i >= 1; i--) {
for(int j = 0; j <= k; j++) {
for(auto v : num[i]) {
if(j - v.first < 0) continue;
if(dp[i + 1][j - v.first]) {
if(dp[i][j] < v.second) {
dp[i][j] = v.second;
lastk[i][j] = j - v.first;
}
}
}
}
}
if(dp[1][k] == 0) cout << "-1" << endl;
else {
int p1 = 1, p2 = k;
cout << dp[p1][p2] - 1;
p2 = lastk[p1][p2];
p1++;
while(p1 <= n) {
cout << dp[p1][p2] - 1;
p2 = lastk[p1][p2];
p1++;
}
}
}