Codeforces Round #637 (Div. 2) D. Nastya and Scoreboard 线性DP

灰太狼 2023-05-21 07:15 6阅读 0赞

题目链接：http://codeforces.com/contest/1341/problem/D  
题意：0~9的数字是由图中的木棒组成的，现在给你若干个显示屏，你可以恰好添加k个木棒  
问你能够组成的最大数字是多少  
思路：num\[i\]\[j\]表示i加j个木棒能凑成的最大的数，我们先初始化num数组，f\[i\]\[j\]表示前i个用了j个木棒的最大值  
我们从后往前考虑，这样保证前面的一定最大，从前往后考虑的话你可以保证最后一位是最优但前面的就不一定了  
所以我们接着转移就可以了。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define po pop_back
    #define pb push_back
    #define mk make_pair
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 1e9 + 7;
    const int maxn = 2e3 + 10;
    const int inf = 0x3f3f3f3f;
    const ll linf = 0x3f3f3f3f3f3f3f3f;
    map<int, string> mp;
    int a[maxn], num[200][10]; //num[i][j]表示i加j个木棒能凑成的最大的数
    int f[maxn][maxn], p[maxn][maxn]; //f[i][j]表示前i个用了j个木棒的最大值
    
    void init()
    {
        memset(num, -1, sizeof(num));
        mp[0] = "1110111", mp[1] = "0010010", mp[2] = "1011101", mp[3] = "1011011", mp[4] = "0111010";
        mp[5] = "1101011", mp[6] = "1101111", mp[7] = "1010010", mp[8] = "1111111", mp[9] = "1111011";
        for(int i = 0; i < (1 << 7); ++i)
        {
            for(int j = 0; j <= 9; ++j)
            {
                int flag = 0;
                string s1 = mp[j];
                for(int k = 0; k < 7; ++k)
                {
                    if(s1[k] == '0' && (i & (1 << (6 - k))))
                    {
                        flag = -1;
                        break;
                    }
                    else if(s1[k] == '1' && !(i & (1 << (6 - k))))
                        ++flag;
                }
                if(flag != -1) num[i][flag] = j;
            }
        }
    }
    
    int main()
    {
        init();
    	int n, m;
    	scanf("%d%d", &n, &m);
    	for(int i = 1; i <= n; ++i)
        {
            string s;
            cin >> s;
            int tmp = 0;
            for(int j = 0; j < 7; ++j) tmp = tmp * 2 + (s[j] == '1');
            a[i] = tmp;
        }
        memset(f, -1, sizeof(f));
        f[n + 1][0] = 0;
        for(int i = n; i >= 1; --i)
        {
            for(int j = 0; j <= m; ++j)
            {
                int tmp = -1;
                for(int k = max(0, j - 7); k <= j; ++k)
                {
                    if(f[i + 1][k] != -1 && num[a[i]][j - k] != -1 && num[a[i]][j - k] > f[i][j])
                        f[i][j] = num[a[i]][j - k], p[i][j] = j - k;
                }
            }
        }
        if(f[1][m] == -1) printf("-1\n");
        else
        {
            int pos = m;
            for(int i = 1; i <= n; ++i)
            {
                printf("%d", f[i][pos]);
                pos -= p[i][pos];
            }
        }
    	return 0;
    }