Codeforces Round #637 (Div. 1)

又掉紫，确实第一次上橙没这么快稳定水平。

比赛的时候有两个bug，发现了其中一个bug。

第一个bug是：-INF乘以10溢出，发现之后改成了-1000。

第二个bug是：把dp值为0的也变成了-INF（或者-1000）。

反思之后，觉得应该这样写：

int n, k;
int dp[2005][2005], dpx[2005];
int dppre[2005][2005], dpans[2005][2005];

int ans[2005];

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

int tch[15];
int rch[2005];

int ReadBinary() {
    int res = 0;
    char ch = getchar();
    while(!isdigit(ch))
        ch = getchar();
    while(isdigit(ch)) {
        res = res * 2 + ch - '0';
        ch = getchar();
    }
    return res;
}

int top;
char Getchar(int id) {
    return s[id][top++];
}

int ReadBinaryID(int id) {
    top = 0;
    int res = 0;
    char ch = Getchar(id);
    while(!isdigit(ch))
        ch = Getchar(id);
    while(isdigit(ch)) {
        res = res * 2 + ch - '0';
        ch = Getchar(id);
    }
    return res;
}

int dis[1 << 7][15];

void TestCase() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i <= 9; ++i)
        tch[i] = ReadBinaryID(i);
    for(int i = 1; i <= n; ++i)
        rch[i] = ReadBinary();
    memset(dis, -INF, sizeof(dis));
    for(int i = 0; i < (1 << 7); ++i) {
        for(int j = 0; j <= 9; ++j) {
            int cnt = 0;
            for(int k = 0; k < 7; ++k) {
                if(((i >> k) & 1) == ((tch[j] >> k) & 1))
                    continue;
                if(((i >> k) & 1) == 1) {
                    cnt = -INF;
                    break;
                }
                ++cnt;
            }
            dis[i][j] = cnt;
        }
    }
    memset(dp, -1, sizeof(dp));
    memset(dppre, -1, sizeof(dppre));
    memset(dpans, -1, sizeof(dpans));
    dp[0][k] = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= 9; ++j) {
            int tmpdis = dis[rch[i]][j];
            if(tmpdis == -INF)
                continue;
            for(int ki = tmpdis; ki <= k; ++ki) {
                if(dp[i - 1][ki] < 0)
                    continue;
                if(dp[i - 1][ki] * 10 + j > dp[i][ki - tmpdis]) {
                    dp[i][ki - tmpdis] = dp[i - 1][ki] * 10 + j;
                    dppre[i][ki - tmpdis] = ki;
                    dpans[i][ki - tmpdis] = j;
                }
            }
        }
        for(int ki = 0; ki <= k; ++ki)
            dpx[ki] = dp[i][ki];
        sort(dpx, dpx + k + 1);
        int ck = unique(dpx, dpx + k + 1) - dpx;
        for(int ki = 0; ki <= k; ++ki)
            dp[i][ki] = (dp[i][ki] < 0) ? (-1) : (lower_bound(dpx, dpx + ck, dp[i][ki]) - dpx);
    }
    if(dp[n][0] < 0) {
        puts("-1");
        return;
    } else {
        int atop = 0, curk = 0;
        for(int i = n; i >= 1; --i) {
            ans[++atop] = dpans[i][curk];
            curk = dppre[i][curk];
        }
        for(int i = n; i >= 1; --i)
            printf("%d", ans[i]);
        puts("");
        return;
    }
}

先枚举预处理把当前的位图还原出0~9的数字是否可行以及可行时消耗多少个k。

这道题假如不溢出整数，就是随便用个max就可以转移出答案，但是这里溢出整数。由dp的性质可以知道，高位的大小区别对低位的影响相同，所以可以逐个把高位的数字进行离散化（使用dpx数组进行辅助离散化）。然后记录一下dp转移的信息，包括“上一步是哪个状态（使用dppre数组进行记录）”，以及“上一步是走哪个数字到这一步（使用dpans数组进行记录）”。