题解：CF1340B Nastya and Scoreboard

Ren_Tongcai · 2025-12-17 15:56:35 · 题解

蒟蒻的第一篇题解 qwq

借鉴自老师的思路和大家分享一下这道题的做法

题意分析

相信题目意思大家都理解了，这边放一个题目传送门大家自己看吧

洛谷题面 // CF题面

每个数字由 7 段数码管组成，当前状态是 7 位二进制串（0 = 关，1 = 开）。我们需要：

把每个位置的当前状态，转换成 0-9 中的某个数字；
转换时只能打开段（不能关闭已开的段），且所有位置的 “打开段数之和” 恰好为 k；
最终构造出字典序最大的 n 位数字（即高位尽可能选大的数）。

简单来讲，这道题有一个主要的策略：

在后面可以用完操作次数的前提下，从左往右让当前数字尽可能大即可。

预处理一下转换所需打开的段数

遍历 7 个段：若当前段是 “开（ 1 ）” 但目标数字 j 的对应段是 “关（ 0 ）”，说明需要关闭段（题目不允许），就直接返回 -1（不可转换）；
否则的话，统计 “当前段关、目标段开” 的数量（即需要打开的段数）。

DP 部分

定义 dp[i][j] 表示：区间 [ i , n ]内用了 j 次操作的可行性，可行值为 1 ，不可行值为 0 。

初始化：dp[n+1][0] = 1（处理完所有 n 个位置后，恰好使用 0 次）。
状态转移：从后往前遍历（因为构造最大数时要优先确定高位，而 DP 需要依赖后续位置的状态）：对于第 i 个位置，枚举当前已用次数 j，再枚举目标数字 x（0-9）：

若 a[i] 可转换成 x，定义转换成本为 c，且 j \ge c；
若 dp[i+1][j-c] 是合法状态，则 dp[i][j] 也合法。

构造最大数字

在 DP 验证 “存在合法方案” 后，用 cnt 表示剩余的转换次数，从前到后构造每个位置的数字：

对于第 i 个位置，从 9 到 0 枚举数字 x（优先选大的数）；
若 a[i] 可转换成 x（成本为 c），且剩余可用次数 cnt \ge c，且 dp[i+1][cnt - c] 合法；
则选择 x 作为当前位，更新剩余可用次数 cnt 减去使用的次数 c ，继续处理下一位。

最后就是一些写代码时要注意的问题，特别注意DP时数组下标出现减法要注意判断是否<0，否则会出错。

请大家梳理一下思路试着自己写一写各个部分的代码，实在遇到问题可以参考以下代码

代码

#include<bits/stdc++.h>
using namespace std;
string s[10]={"1110111","0010010","1011101","1011011",
"0111010","1101011","1101111","1010010","1111111","1111011"};
string a[2010],ans;
int n,k,dp[2010][2010];
int calc(int i,int j) //a[i] -> 数字 j 的操作数 
{
    int cnt=0;
    for(int p=0;p<7;p++)
    {
        if(a[i][p]=='1'&&s[j][p]=='0') 
        {
            return -1;
        }
        cnt+=(a[i][p]!=s[j][p]);
    }
    return cnt;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[n+1][0]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=0;j<=k;j++)
        {
            for(int x=0;x<=9;x++)
            {
                int c=calc(i,x);
                if(c==-1||j-c<0) continue;
                dp[i][j]=max(dp[i][j],dp[i+1][j-c]);
            }
        }
    }
    if(!dp[1][k])
    {
        cout<<-1;
        return 0;
    }
    int cnt=k;
    for(int i=1;i<=n;i++)
    {
        for(int j=9;j>=0;j--) //试填 j 到第 i 个位置 
        {
            int c=calc(i,j); 
            if(c!=-1&&cnt-c>=0&&dp[i+1][cnt-c]) //能填 j 
            {
                ans+=(char)('0'+j);
                cnt-=c;
                break; 
            }
        }
    }
    cout<<ans;
    return 0;
}

就这样啦希望能够帮助到大家 qwq