题解 | 小红的双生数

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int cmpPair(int d, char a, char b)
{
    int x = a - '0';
    int y = b - '0';

    if(d < x) return -1;
    if(d > x) return 1;

    if(d < y) return -1;
    if(d > y) return 1;

    return 0;
}

string buildMinLonger(int len)
{
    string res = "";
    int prev = -1;

    for(int i = 0; i < len / 2; i++)
    {
        int d;
        if(i == 0) d = 1;
        else
        {
            if(prev != 0) d = 0;
            else d = 1;
        }

        res += char('0' + d);
        res += char('0' + d);
        prev = d;
    }

    return res;
}

int main()
{
    string x;
    cin >> x;

    int n = x.size();

    if(n % 2 == 1)
    {
        cout << buildMinLonger(n + 1) << endl;
        return 0;
    }

    int m = n / 2;
    vector<vector<int> > dp(m + 1, vector<int>(11, 0));

    for(int prev = 0; prev <= 10; prev++)
    {
        dp[m][prev] = 1;
    }

    for(int pos = m - 1; pos >= 0; pos--)
    {
        char a = x[2 * pos];
        char b = x[2 * pos + 1];

        for(int prev = 0; prev <= 10; prev++)
        {
            dp[pos][prev] = 0;

            for(int d = 0; d <= 9; d++)
            {
                if(pos == 0 && d == 0) continue;
                if(prev != 10 && d == prev) continue;

                int c = cmpPair(d, a, b);
                if(c < 0) continue;

                if(c > 0)
                {
                    dp[pos][prev] = 1;
                    break;
                }
                else
                {
                    if(dp[pos + 1][d])
                    {
                        dp[pos][prev] = 1;
                        break;
                    }
                }
            }
        }
    }

    if(!dp[0][10])
    {
        cout << buildMinLonger(n + 2) << endl;
        return 0;
    }

    string ans = "";
    int prev = 10;
    bool same = true;

    for(int pos = 0; pos < m; pos++)
    {
        if(!same)
        {
            int d;
            for(d = 0; d <= 9; d++)
            {
                if(pos == 0 && d == 0) continue;
                if(prev != 10 && d == prev) continue;
                break;
            }

            ans += char('0' + d);
            ans += char('0' + d);
            prev = d;
            continue;
        }

        char a = x[2 * pos];
        char b = x[2 * pos + 1];

        for(int d = 0; d <= 9; d++)
        {
            if(pos == 0 && d == 0) continue;
            if(prev != 10 && d == prev) continue;

            int c = cmpPair(d, a, b);
            if(c < 0) continue;

            if(c > 0)
            {
                ans += char('0' + d);
                ans += char('0' + d);
                prev = d;
                same = false;
                break;
            }
            else
            {
                if(dp[pos + 1][d])
                {
                    ans += char('0' + d);
                    ans += char('0' + d);
                    prev = d;
                    break;
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}