linkkkk
题意：
给出n个灯，再点亮恰好k节灯管，问能够组成的最大数，允许有前导零。
思路：
d p [ i ] [ j ]表示从i − n花费j根灯管能够在i得到的最大数.
代码：
string str[]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011" }; int dp[2100][2100]; string s[2100]; int cul(string s,int id){ int ans=0; for(int i=0;i<s.size();i++){ if(s[i]=='1'&&str[id][i]=='0') return -1; else if(s[i]=='0'&&str[id][i]=='1') ans++; } return ans; } int main(){ int n=read,k=read; rep(i,1,n){ cin>>s[i]; } memset(dp,-1,sizeof dp); //dp[i][j]表示从i~n花费j根灯管能够在第i得到的最大数 for(int i=n;i;i--){ if(i==n){ for(int j=0;j<10;j++){ int tmp=cul(s[i],j); if(tmp==-1) continue;//无法变成这个数 dp[i][tmp]=max(dp[i][tmp],j); } } else{ for(int j=0;j<10;j++){ int tmp=cul(s[i],j); if(tmp==-1) continue; for(int t=tmp;t<=k;t++) if(dp[i+1][t-tmp]!=-1) dp[i][t]=max(dp[i][t],j); } } } if(dp[1][k]==-1) puts("-1"); else{ int now=k; for(int i=1;i<=n;i++){ cout<<dp[i][now]; now-=cul(s[i],dp[i][now]); } } return 0; } /** **/
