codeforces1341 D. Nastya and Scoreboard（dp + 贪心）
D. Nastya and Scoreboard
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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 77 segments, which can be turned on or off to display different numbers. The picture shows how all 1010 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 kk 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 kk sticks (which are off now)?
It is allowed that the number includes leading zeros.
Input
The first line contains integer nn (1≤n≤2000)(1≤n≤2000) — the number of digits on scoreboard and kk (0≤k≤2000)(0≤k≤2000) — the number of segments that stopped working.
The next nn lines contain one binary string of length 77, the ii-th of which encodes the ii-th digit of the scoreboard.
Each digit on the scoreboard consists of 77 segments. We number them, as in the picture below, and let the ii-th place of the binary string be 00 if the ii-th stick is not glowing and 11 if it is glowing. Then a binary string of length 77 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 00 to 99 inclusive.
Output
Output a single number consisting of nn digits — the maximum number that can be obtained if you turn on exactly kk sticks or −1−1, if it is impossible to turn on exactly kk sticks so that a correct number appears on the scoreboard digits.
Examples
input
Copy
1 7 0000000
output
Copy
8
input
Copy
2 5 0010010 0010010
output
Copy
97
input
Copy
3 5 0100001 1001001 1010011
output
Copy
-1
Note
In the first test, we are obliged to include all 77 sticks and get one 88 digit on the scoreboard.
In the second test, we have sticks turned on so that units are formed. For 55 of additionally included sticks, you can get the numbers 0707, 1818, 3434, 4343, 7070, 7979, 8181 and 9797, of which we choose the maximum — 9797.
In the third test, it is impossible to turn on exactly 55 sticks so that a sequence of numbers appears on the scoreboard.
题意：
每个数字由7根显示管组成，按顺序给出每个显示屏现在的状态，0表示显示管关闭，1表示打开；现在从原有的基础上精确地打开 k 个显示管，问是否可以显示出一串数字，如果可以，求出能显示的最大的数字
思路：
（我没有想到dp，爆搜T了……
dp：
dp[ i ][ j ]表示从第 i 个数字开始到最后，点亮 j 个显示管，能否显示出数字。（从后向前）
现预处理出原始的每个显示屏变到某个数字需要点亮的显示管数，或者不可以变成某个数字
贪心时从前向后，从9到0（保证数字尽量大）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int N = 2e3 + 10;
string ss[10] = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
string s[N];
int n, k, cn[N][10];
bool dp[N][N];
void init()
{
memset(cn, 0, sizeof(cn));
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j < 10; ++j)
{
for(int k = 0; k < 7; ++k)
{
if(s[i][k] == '1' && ss[j][k] == '0')
{
cn[i][j] = -1;
break;
}
if(s[i][k] != ss[j][k])
{
cn[i][j]++;
}
}
// cout<<cn[i][j]<<' ';
}
// cout<<'\n';
}
}
bool solve()
{
memset(dp, 0, sizeof(dp));
dp[n + 1][0] = 1;
for(int i = n; i; --i)
{
for(int j = 0; j < 10; ++j)
{
if(cn[i][j] != -1)
{
for(int u = cn[i][j]; u <= k; ++u)
{
dp[i][u] |= dp[i + 1][u - cn[i][j]];
}
}
}
}
if(!dp[1][k])
return 0;
else
return 1;
}
int main()
{
while(~scanf("%d%d", &n, &k))
{
for(int i = 1; i <= n; ++i)
{
cin >> s[i];
}
init();
if(!solve())
cout<<-1<<'\n';
else
{
int tmp = k;
vector<int>vec;
for(int i = 1; i <= n; ++i)
{
for(int j = 9; j >= 0; --j)
{
if(cn[i][j] != -1 && tmp >= cn[i][j] && dp[i + 1][tmp - cn[i][j]])
{
tmp -= cn[i][j];
vec.push_back(j);
break;
}
}
}
for(int i = 0; i < vec.size(); ++i)
{
cout<<vec[i];
}
cout<<'\n';
vec.clear();
}
}
return 0;
}
dfs剪枝：
等会来补
