题面

Prob1

Prob2

题意

数位板如题面所示，每个数位板由 7 个灯管组成

给定 n 个数位板此时的状态，1 为亮 0 为暗

要求严格再点亮 k 个灯管，使得数位板上能够呈现出数字，且这个数字最大

如果无法呈现出数字，输出 -1，否则，输出操作后呈现的数字

答案允许存在前导 0

解题思路

当时只想着贪心过，结果找到反例没法解决，没往dp预处理上想

看了下通过的大佬的代码才知道可以先预处理出能否构成数字再去贪心

总体思路如下——

先预处理出输入的每个数位板，将其变成0~9这些数字分别需要点亮的灯管数量，记录在 cost[i][j] 中

然后从后往前动态规划，使用 dp[i][j] 来表示从第 i 个数位板开始到最后一个数位板，严格只点亮 j 根灯管能否呈现出数字（bool类型）

接着通过 dp[1][k] 的值来判断题目的要求能否满足，如果为false直接输出 -1（ dp[1][k] 即表示所有数位板严格只点亮 k 根灯管能否呈现出数字）

最后，因为答案要求数字尽可能最大，所以让大的数位尽可能靠前，从前往后顺序处理后输出即可

代码实现

首先手打0~9的数位板样式

char num[10][10]=
{
    "1110111",
    "0010010",
    "1011101",
    "1011011",
    "0111010",
    "1101011",
    "1101111",
    "1010010",
    "1111111",
    "1111011"
}; //0~9的数码板样式

然后预处理 cost 数组

输入当前数位板状态后循环 0~9 来与样式对比

如果数位板 i 某位为 0，数字 j 对应位置为 1，说明要想变成数字 j 需要多点亮一根灯管，操作数 +1
如果数位板 i 某位为 1，数字 j 对应位置为 0，由于题目要求只能点亮不能关闭，所以不存在这种操作，置 -1

for(i=1;i<=n;i++)
{
    cin>>str;
    for(j=0;j<=9;j++)
    {
        for(u=0;u<7;u++)
        {
            if(str[u]=='0'&&num[j][u]=='1')
                cost[i][j]++; //如果当前为0但是数字j为1，操作数+1
            else if(str[u]=='1'&&num[j][u]=='0')
            {
                cost[i][j]=-1; //如果当前为1但是数字j为0，则无法变成j，置-1
                break;
            }
        }
    }
}

然后开始动态规划

因为第 n+1 个数位板不存在，所以从最后一个数位板到第 n+1 个数位板点亮 0 根灯管需要特殊初始化为 true

然后从第 n 个数位板开始往前处理

假设此时从后往前到第 i+1 个数位板点亮 u 根灯管能够表示出数字，即 dp[i+1][u] == true

根据 cost 数组，假设如果此时能够将第 i 个数位板变成 j ，且操作数为 cost[i][j]

则说明从后往前到第 i 个数位板点亮 u+cost[i][j] 根灯管能够表示出数字

于是得到状态转移方程为

dp[i][u+cost[i][j]] |= dp[i+1][u]

j 循环 0~9，u 从 0 循环至 k-cost[i][j]

或者使用方程

dp[i][u] |= dp[i+1][u-cost[i][j]]

j 循环 0~9，u 从 cost[i][j] 循环至 k

dp[n+1][0]=true; //初始化 第n+1位即没有数码板时点亮0根灯管 置true
for(i=n;i;i--) //从后往前处理
{
    for(j=0;j<=9;j++)
    {
        if(cost[i][j]==-1) //第i个数码板无法变成数字j
            continue;
        for(u=cost[i][j];u<=k;u++)
        {
            dp[i][u]|=dp[i+1][u-cost[i][j]]; //状态转移（取或运算以保持）
        }
    }
}

然后判断 dp[1][k] 是否为 false，是则直接输出 -1 并结束程序

最后开始从前往后贪心

答案尽可能大，所以要让大数位在前

（这一步让 k 作为一个变量，将其意义变成“剩余的操作数”）

i 从 1 到 n 循环，枚举 j 时要从 9 到 0 循环

如果第 i 位无法变成 j 则跳过

否则检查剩余操作数 k 是否能够支持让第 i 位变成 j ，且变成 j 后剩余操作数又能否支持第 i+1 位开始到最后一位呈现出数字

如果两个条件都满足，则第 i 位就变成 j ，剩余操作数减去 cost[i][j]

依次处理即可

for(i=1;i<=n;i++)
{
    for(j=9;j>=0;j--) //贪心，要使答案数字最大，尽量大数位在前
    {
        if(cost[i][j]==-1)
            continue;
        if(k>=cost[i][j]&&dp[i+1][k-cost[i][j]]) //如果k能满足在第i位构造出数字j，且还能支持i+1位以后构造出数字
        {
            ans[i]=j+'0'; //j即为第i位的答案
            k-=cost[i][j];
            break;
        }
    }
}

完整代码

(31ms/1000ms)

#include<bits/stdc++.h>
using namespace std;

char num[10][10]=
{
    "1110111",
    "0010010",
    "1011101",
    "1011011",
    "0111010",
    "1101011",
    "1101111",
    "1010010",
    "1111111",
    "1111011"
}; //0~9的数码板样式

char str[10],ans[2050];

int cost[2050][10]; //cost[i][j] 第i个数字变成j的操作数

bool dp[2050][2050]; //dp[i][j] 从后开始往前到第i个数码板，点亮j根能否构造出数字

void solve()
{
    int n,k,d,i,j,u;
    cin>>n>>k;

    for(i=1;i<=n;i++)
    {
        cin>>str;
        for(j=0;j<=9;j++)
        {
            for(u=0;u<7;u++)
            {
                if(str[u]=='0'&&num[j][u]=='1') //如果当前为0但是数字j为1，操作数+1
                    cost[i][j]++;
                else if(str[u]=='1'&&num[j][u]=='0') //如果当前为1但是数字j为0，则无法变成j，置-1
                {
                    cost[i][j]=-1;
                    break;
                }
            }
        }
    }

    dp[n+1][0]=true; //初始化 第n+1位即没有数码板时点亮0根灯管 置true
    for(i=n;i;i--) //从后往前处理
    {
        for(j=0;j<=9;j++)
        {
            if(cost[i][j]==-1) //第i个数码板无法变成数字j
                continue;
            for(u=cost[i][j];u<=k;u++)
            {
                dp[i][u]|=dp[i+1][u-cost[i][j]]; //换言之，如果到第i+1位点亮u根能够构造出数字，那么到第i位点亮u+cost[i][j]根也能构造出数字
            }
        }
    }

    if(!dp[1][k]) //全部处理完后如果点亮k根无法构造出数字，则
    {
        cout<<"-1
";
        return;
    }

    for(i=1;i<=n;i++)
    {
        for(j=9;j>=0;j--) //贪心，要使答案数字最大，尽量大数位在前
        {
            if(cost[i][j]==-1)
                continue;
            if(k>=cost[i][j]&&dp[i+1][k-cost[i][j]]) //如果k能满足在第i位构造出数字j，且还能支持i+1位以后构造出数字
            {
                ans[i]=j+'0'; //j即为第i位的答案
                k-=cost[i][j];
                break;
            }
        }
    }

    ans[n+1]='';
    cout<<(ans+1)<<'
';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}