題目大意：給出 n 個二進制數(shù)字，1 ~ n 分別表示從最高位到最低位的數(shù)字，每個二進制數(shù)字的長度都為 7 ，分別表示相應(yīng)位置是否被點亮
?現(xiàn)在總共需要再點亮 k 個位置，問能否有一種方案，使得 1 ~ n 的所有數(shù)字都合理，且組合出來的數(shù)最大
題目分析：因為 n 和 k 給的范圍都是 2e3 ，不難想到 dp[ i ][ j ] 代表的是到了第 i 個數(shù)，還可以點亮 j 個位置時是否可行，這個 dp 可以根據(jù)完全背包的原理進行轉(zhuǎn)移，同時可以預(yù)處理出一個 val[ i ][ num ] 數(shù)組，代表的是第 i 個數(shù)變成 num 的代價，num ∈ [ 0 , 9 ] ，dp 轉(zhuǎn)移好后貪心去找就行了
需要注意的是，這個 dp 是需要從 n + 1 向前轉(zhuǎn)移的，也就是從 dp[ n + 1 ][ 0 ] 開始轉(zhuǎn)移，對于這里我的理解是，可以將 [ n + 1 ][ 0 ] 這個狀態(tài)視為根節(jié)點，轉(zhuǎn)移的過程可以想象成一個有向圖，這樣點 [ 1 ][ k ] 所表示的狀態(tài)代表的就是一個葉子結(jié)點了，如果 dp[ 1?][ k ] = true 的話，那就說明肯定能找到一條從狀態(tài) [ n + 1 ][ 0 ] 到狀態(tài) [ 1 ][ k ] 的通路，只是這條通路不一定是唯一的，剩下的我們就可以貪心去找了，每次都去找父節(jié)點就好了
代碼： ?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e3+100;const string str[]={"1110111","0010010","1011101","1011011","0111010","1101011","1101111","1010010","1111111","1111011"};string s;int val[N][10],dp[N][N];void init(int pos)
{for(int i=0;i<=9;i++){bool flag=false;int cnt=0;for(int j=0;j<7;j++)if(str[i][j]!=s[j]){if(s[j]=='1'){flag=true;break;}cnt++;}if(flag)val[pos][i]=-1;elseval[pos][i]=cnt;}
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){cin>>s;init(i);}dp[n+1][0]=true;for(int i=n;i>=1;i--)for(int j=0;j<=9;j++){if(val[i][j]==-1)continue;for(int t=val[i][j];t<=k;t++)dp[i][t]|=dp[i+1][t-val[i][j]];}if(!dp[1][k])return 0*puts("-1");string ans;for(int i=1;i<=n;i++)for(int j=9;j>=0;j--)if(val[i][j]!=-1&&k-val[i][j]>=0&&dp[i+1][k-val[i][j]]){k-=val[i][j];ans+=to_string(j);break;}cout<<ans<<endl;return 0;
}
