SRM454 Div1 Medium(500) NumbersAndMatches

NumbersAndMatches

動的計画法。a 本のマッチを加えつつ k 本のマッチを動かして残り d 桁の数字から得られる数字の個数を t[d][k][a] とする。数字 x を y に書き換える際に動かすマッチの本数を u_x,y、加える（負数で取り除く）マッチの本数を v_x,y とする。以下の等式が成り立つ。
　t[d][k][a] = Σ_0≦i≦9 t[d-1][k-u_n,i-v_n,i][a-v_n,i]　　(v_n,i＞0)
　t[d][k][a] = Σ_0≦i≦9 t[d-1][k-u_n,i][a-v_n,i]　　(v_n,i≦0)
ここで、n は N の d 桁目の数字である。場合分けは、ある桁でマッチを取り除き他の桁に加えるという移動を２重に数えないため。

#include <algorithm>

using namespace std;

class NumbersAndMatches
{
public:
    long long differentNumbers( long long N, int K );
    long long BT( int digit, long long N, int K, int diff );
};

long long NumbersAndMatches::differentNumbers( long long N, int K )
{
    //  数字
    //  ┌４┐
    //  ０　１
    //  ├５┤
    //  ２　３
    //  └６┘
    const int number[10][7] = {
        { 1, 1, 1, 1, 1, 0, 1 },    //  0
        { 0, 1, 0, 1, 0, 0, 1 },    //  1
        { 0, 1, 1, 0, 1, 1, 1 },    //  2
        { 0, 1, 0, 1, 1, 1, 1 },    //  3
        { 1, 1, 0, 1, 0, 1, 0 },    //  4
        { 1, 0, 0, 1, 1, 1, 1 },    //  5
        { 1, 0, 1, 1, 1, 1, 1 },    //  6
        { 0, 1, 0, 1, 1, 0, 0 },    //  7
        { 1, 1, 1, 1, 1, 1, 1 },    //  8
        { 1, 1, 0, 1, 1, 1, 1 },    //  9
    };

    //  数字を書き換えるために移動・追加するマッチ数
    struct { int move, add; } match[10][10];

    for ( int i=0; i<10; i++ )
    for ( int j=0; j<10; j++ )
    {
        int d = 0;
        int a = 0;

        for ( int k=0; k<7; k++ )
        {
            if ( number[i][k] > number[j][k] )  d++;
            if ( number[i][k] < number[j][k] )  a++;
        }

        match[i][j].move = min( d, a );
        match[i][j].add = a - d;
    }

    //  桁数
    int digit = 0;
    for ( long long i=1; i<=N; i*=10 )
        digit++;

    //  DP表 [d][k][a]
    //  (a-100) 本のマッチを加えながら下 d 桁の k 本のマッチを動かして
    //  得られる数字の個数
    //  桁間で移動するマッチは追加時にカウント
    static long long table[20][130][200];
    memset( table, 0, sizeof table );

    table[0][0][100] = 1;

    for ( int d=1; d<=digit; d++, N/=10 )
    for ( int k=0; k<=K; k++ )
    for ( int a=0; a<200; a++ )
    {
        for ( int n=0; n<10; n++ )
        {
            int tk = match[N%10][n].move + max( match[N%10][n].add, 0 );
            int ta = match[N%10][n].add;

            if ( 0 <= k-tk  &&
                 0 <= a-ta  &&  a-ta < 200 )
                table[d][k][a] += table[d-1][k-tk][a-ta];
        }
    }

    long long ans = 0;
    for ( int k=0; k<=K; k++ )
        ans += table[digit][k][100];

    return ans;
}