Codeforces Round #637 (Div. 2)-D. Nastya and Scoreboard

这道题昨晚打时tle到自闭，还好最终还是AC了，此题必须得写下题解了。

题意：有n个数字LED灯，现有部分已经亮着，如果能恰好再亮起k个灯管使结果为合法的数字，输出最大的数（允许有前导零），如果不能则输出-1.

思路：使用二维数组lc[i][j]记录第i个LED屏变成j还需要亮起多少的灯管，不能则-1. xs[i]数组记录第i个LED屏已经打开的灯管构成的数字，若不是数字则为-1. minn[i],maxx[i]分别记录从i开始的所有LED屏若要构成合法数字最小/最大一共要再亮起多少灯管（这个很重要，剪枝的关键，也是我一直tle的原因！！！）。 将这些预处理处理完后，就可以开始dfs+剪枝了。每一位数从9-0开始，贪心找尽可能大的数字。ans[i]存第i个LED最终变为的数。
剪枝：如果当前已经使用过的灯管数+minn[i] > k 那么一定不合法，return；
如果当前已经使用过的灯管数+maxx[i] < k 那么一定不合法，return；
如果找到了一组答案，直接退出，因为我们是贪心思想每一位都是从最大的数开始dfs的，那么这个答案一定是最大的，退出dfs。

#include <iostream>
#include <cmath>
//#include<bits/stdc++.h>ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cstring>
using namespace std;
const double pi = acos(-1.0);
typedef long long LL;
const int mod = 100;
char num[10][10]={"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
int check(char p[])
{
    for(int i=0;i<10;i++)
    {
        if(strcmp(num[i],p)==0)   return i;
    }
    return -1;
}
int add(char a[],char b[])
{
    int sum=0;
    for(int i=0;i<7;i++)
    {
        if(a[i]=='1'&&b[i]=='0')    return -1;
        if(a[i]=='0'&&b[i]=='1')    sum++;
    }
    return sum;
}
char s[2010][10];
int n,k;
bool ok=false;
int ans[2010];
int lc[2010][10];
int xs[2010];
int minn[2010];
int maxx[2010];
void dfs(int x,int p)
{
    if(p+minn[x]>k) return;
    if(p+maxx[x]<k) return;
    if(x==n)
    {
        if(p==k)    ok=true;
        return;
    }
    if(p==k)
    {
        for(int i=x;i<n;i++)
        {
            int o=xs[i];
            if(o==-1)   return;
            ans[i]=o;
        }
        ok=true;
        return;
    }
    for(int i=9;i>=0;i--)
    {
        int c=lc[x][i];
        if(c==-1 || c+p>k)   continue;
        ans[x]=i;
        dfs(x+1,p+c);
        if(ok)  return;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        minn[i]=INT_MAX;
        for(int j=0;j<10;j++)
        {
            lc[i][j]=add(s[i],num[j]);
            if(lc[i][j]!=-1)    minn[i]=min(minn[i],lc[i][j]);
            maxx[i]=max(maxx[i],lc[i][j]);
        }
        xs[i]=check(s[i]);
    }
    for(int i=n-2;i>=0;i--)
    {
        minn[i]+=minn[i+1];
        maxx[i]+=maxx[i+1];
    }   
    dfs(0,0);
    if(ok)
    {
        for(int i=0;i<n;i++)
            cout<<ans[i];
        cout<<endl;
    }
    else    cout<<-1<<endl;
    




    int ab;
    cin>>ab;
    return 0;
}