SRM510 Div2 Medium(500) 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; }};