CF1341D. Nastya and Scoreboard（DP）

本文主要是介绍CF1341D. Nastya and Scoreboard（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Denis, after buying flowers and sweets (you will learn about this story in the next task), went to a date with Nastya to ask her to become a couple. Now, they are sitting in the cafe and finally… Denis asks her to be together, but … Nastya doesn’t give any answer.

The poor boy was very upset because of that. He was so sad that he punched some kind of scoreboard with numbers. The numbers are displayed in the same way as on an electronic clock: each digit position consists of 7 segments, which can be turned on or off to display different numbers. The picture shows how all 10 decimal digits are displayed:

After the punch, some segments stopped working, that is, some segments might stop glowing if they glowed earlier. But Denis remembered how many sticks were glowing and how many are glowing now. Denis broke exactly 𝑘 segments and he knows which sticks are working now. Denis came up with the question: what is the maximum possible number that can appear on the board if you turn on exactly 𝑘 sticks (which are off now)?

It is allowed that the number includes leading zeros.

Input
The first line contains integer 𝑛 (1≤𝑛≤2000) — the number of digits on scoreboard and 𝑘 (0≤𝑘≤2000) — the number of segments that stopped working.

The next 𝑛 lines contain one binary string of length 7, the 𝑖-th of which encodes the 𝑖-th digit of the scoreboard.

Each digit on the scoreboard consists of 7 segments. We number them, as in the picture below, and let the 𝑖-th place of the binary string be 0 if the 𝑖-th stick is not glowing and 1 if it is glowing. Then a binary string of length 7 will specify which segments are glowing now.

Thus, the sequences “1110111”, “0010010”, “1011101”, “1011011”, “0111010”, “1101011”, “1101111”, “1010010”, “1111111”, “1111011” encode in sequence all digits from 0 to 9 inclusive.

Output
Output a single number consisting of 𝑛 digits — the maximum number that can be obtained if you turn on exactly 𝑘 sticks or −1, if it is impossible to turn on exactly 𝑘 sticks so that a correct number appears on the scoreboard digits.

Examples
inputCopy
1 7
0000000
outputCopy
8
inputCopy
2 5
0010010
0010010
outputCopy
97
inputCopy
3 5
0100001
1001001
1010011
outputCopy
-1
Note
In the first test, we are obliged to include all 7 sticks and get one 8 digit on the scoreboard.

In the second test, we have sticks turned on so that units are formed. For 5 of additionally included sticks, you can get the numbers 07, 18, 34, 43, 70, 79, 81 and 97, of which we choose the maximum — 97.

In the third test, it is impossible to turn on exactly 5 sticks so that a sequence of numbers appears on the scoreboard.

题意：
每个数字由一定的棍子组成，给出初始每个位置的棍子组成。
再给你 $k$ 个额外棍子，求最后组成的最大数。

思路：
将数组反转一下。
定义 $d p [i] [j]$ 为对于前 $i$ 个位置，使用了 $j$ 个额外棍子能否组成数。转移过程记录状态。
最后输出结果的时候，尽量从大的数组往前找。复杂度是 $10 * n * k$

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <string>
#include <iostream>using namespace std;
typedef long long ll;const int maxn = 2005;int f[maxn][maxn],pre[maxn][maxn];
string s[10] = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
string a[maxn];
int c[maxn][maxn];bool check(string x) {for(int i = 0;i <= 9;i++) {int flag = 1;for(int j = 0;j <= 6;j++) {if(x[j] == '1' && s[i][j] == '0') {flag = 0;break;}}if(flag) return true;}return false;
}int dis(string x,string y) {int num = 0;for(int j = 0;j <= 6;j++) {if(x[j] == '1' && y[j] == '0') {return -1;}else if(x[j] == '0' && y[j] == '1') {num++;}}return num;
}int main() {int n,k;scanf("%d%d",&n,&k);memset(f,-1,sizeof(f));int flag = 1;for(int i = 1;i <= n;i++) {cin >> a[i];flag = check(a[i]);}if(!flag) {printf("-1\n");return 0;}reverse(a + 1,a + 1 + n);f[0][0] = 1;for(int i = 1;i <= n;i++) {for(int j = 0;j <= 9;j++) {c[i][j] = dis(a[i],s[j]);}}for(int i = 1;i <= n;i++) {for(int j = 0;j <= k;j++) {for(int q = 0;q <= 9;q++) {int d = c[i][q];if(d == -1) continue;if(j < d) continue;if(f[i - 1][j - d] != -1) {f[i][j] = 1;pre[i][j] = q;}}}}
//    printf("%d %d\n",dis(a[3],s[0]),dis(a[2],s[0]));if(f[n][k] == -1) {printf("-1\n");return 0;}int num = k;for(int i = n;i >= 1;i--) {int x = pre[i][num];int d = dis(a[i],s[x]);num -= d;printf("%d",x);}return 0;
}