SRM510 Div2 Medium(500) TheLuckyGameDivTwo

TheLuckyGameDivTwo

Brusがある区間を選択したときに、Lucky numberの個数がいくつになるかを覚えておけば、TLEにならない。

#include <algorithm>
using namespace std;

int jLen, bLen;
int memo[4748];

bool lucky( int x )
{
    for ( ; x>0; x/=10 )
        if ( x%10!=4 && x%10!=7 )
            return false;
    return true;
}

int brus( int p )
{
    if ( memo[p]>=0 )
        return memo[p];

    int ans = 0;
    for ( int i=0; i<bLen; i++ )
        if ( lucky(p+i) )
            ans++;

    return memo[p] = ans;
}

int john( int p )
{
    int ans = brus(p);
    for ( int i=p+1; i+bLen<=p+jLen; i++ )
        ans = min( ans, brus(i) );
    return ans;
}

class TheLuckyGameDivTwo{public:
int find( int a, int b, int jLen, int bLen )
{
    ::jLen = jLen;
    ::bLen = bLen;
    for ( int i=0; i<sizeof memo/sizeof memo[0]; i++ )
        memo[i] = -1;

    int ans = john(a);
    for ( int i=a+1; i+jLen<=b+1; i++ )
        ans = max( ans, john(i) );
    return ans;
}};