D. Nastya and Scoreboard

Nastya and Scoreboard"/>

D. Nastya and Scoreboard

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 k 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 k sticks (which are off
now)?

It is allowed that the number includes leading zeros.

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

The next n lines contain one binary string of length 7, the i-th of
which encodes the i-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 i-th place of the binary string
be 0 if the i-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 n digits — the maximum
number that can be obtained if you turn on exactly k sticks or −1, if
it is impossible to turn on exactly k 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.

#include<iostream>
#include<assert.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
string digit[]= {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
int is[2001][2001],n,ans[2001],test[2001];
string store[2001];
bool flag=false;
void dfs(int pos,int ret)
{if(ret<0||flag)return;if(pos==n){if(ret==0){flag=true;for(int i=1; i<=n; i++)cout<<ans[i];cout<<endl;return ;}elsereturn ;}if(is[pos][ret])return ;for(int i=9; i>=0; i--){int diffs=0;for(int j=0; j<8; j++)if(store[pos][j]=='0'&&digit[i][j]=='1')diffs++;else if(store[pos][j]=='1'&&digit[i][j]=='0'){diffs=0x3f3f3f3f;break;}ans[pos+1]=i;dfs(pos+1,ret-diffs);}if(!flag)is[pos][ret]=1;
}
int main()
{int ret;cin>>n>>ret;for(int i=0; i<n; i++)cin>>store[i];dfs(0,ret);if(!flag){cout<<-1<<endl;}
}

我本来的思路是完全背包，但是考虑背包的值最多2000为，就用了string作为值，结果超时，官方题解则只是用完全背包容找出了1~n个字符转化容量的可能性，然后依据可能性找最优值，骚操作学到了。

官方题解。

#include<iostream>
#include<assert.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
vector<string> digits = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,k;cin>>n>>k;vector<string>s(n);vector<vector<int> >dist(n,vector<int>(10));//初始化使使每一个子vector初始化为10个大小for(int i=0; i<n; i++) //统计每个字符串转化为数字的次数-1为不可能{cin>>s[i];for(int d=0; d<10; d++)for(int j=0; j<7; j++){char x=s[i][j];char y=digits[d][j];if(x=='1'&&y=='0'){dist[i][d]=-1;break;}if(x=='0'&&y=='1')++dist[i][d];}}vector<vector<int>> dp(n+1,vector<int>(k+1));//完全背包dp[n][0]=1;for(int i=n; i>0; i--){for(int j=0; j<=k; j++) //枚举每一个背包容积可能{if(dp[i][j])for(int d=0; d<10; d++)if(dist[i-1][d]!=-1&&j+dist[i-1][d]<=k)dp[i-1][j+dist[i-1][d]]=1;//说明可以装到该容积}}if(dp[0][k]==0){cout<<-1<<endl;return 0;}for(int i=0; i<n; i++)//从可能中找最值{int now=-1;for(int d=9; d>=0; d--){if(dist[i][d]!=-1&&k>=dist[i][d]&&dp[i+1][k-dist[i][d]])//从小到大回溯如果dp[i+1][k-dist[i][d]]存在说明这条路行得通{now=d;k-=dist[i][d];break;}}cout<<now;}cout<<endl;
}