CF#637 D. Nastya and Scoreboard DP

D. Nastya and Scoreboard

题意

一块电子屏幕上有n个数字。

每个数字是通过这样7个线段显示的，现在你不小心打坏了k个线段，给出打坏之后的n个数字的显示方式，问之前的屏幕表示的最大数字是多少？

思路

看数据范围感觉就是DP。

我们把n个数字先倒过来，要尽可能的让后面的数字大。

dp[i][j][k]表示前i个数字打坏了j个线段最后一个数字为k是否可行。

对于第i个数字，枚举可以变成的数字。

回溯一下即可。

代码

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

const int N=2e5+10;

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

char str[N][10];

char num[10][10]= {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};

int dp[2010][2010][10];

int main()

{

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=n; i>=1; i--)//先把n个数字倒过来

        scanf("%s",str[i]);

    for(int i=0; i<10; i++)

        dp[0][0][i]=1;

    for(int i=1; i<=n; i++)//前i个数字

    {

        for(int j=0; j<=k; j++)//打坏了j个线段

        {

            for(int l=0; l<=9; l++)//第i个数字为l是否可行

            {

                int flag=0,sum=0;//分别表示是否可以变成l，以及需要的线段数量

                for(int m=0; m<7; m++)

                {

                    if(num[l][m]<str[i][m])

                    {

                        flag=1;

                        break;

                    }

                    sum+=num[l][m]-str[i][m];

                }

                if(flag||j<sum) continue;//不能变成，或者需要的线段数量比打坏的多

                for(int m=0; m<10; m++)//判断当前是否可行

                {

                    if(dp[i-1][j-sum][m])

                    {

                        dp[i][j][l]=1;

                        break;

                    }

                }

            }

        }

    }

    int sign=0;

    for(int i=0;i<=9;i++)

    {

        if(dp[n][k][i])

        {

            sign=1;

            break;

        }

    }

    if(sign)

    {

        for(int i=n;i;i--)

        {

            for(int j=9;j>=0;j--)//每一位选择最大的一个

            {

                if(dp[i][k][j])

                {

                    printf("%d",j);

                    for(int l=0;l<7;l++)

                        k-=num[j][l]-str[i][l];

                    break;

                }

            }

        }

        printf("\n");

    }

    else printf("-1\n");

    return 0;

}

博客

巴特西

CF#637 D. Nastya and Scoreboard DP

D. Nastya and Scoreboard

题意

思路

代码

最新文章

热门文章