CFR 505 C. Mr. Kitayuta, the Treasure Hunter ( Memoization DP )

Problem - C - Codeforces
題意：
給一堆節點，表示節點上有寶石，重複輸入節點代表有多少寶石，和一開始跳躍的距離 D，代表初始時在 D 編號的島上，且最後一次跳躍的距離是 D。接著每次移動可以選擇移動最後一次移動的長度 -1 / 0 / +1，但不能不移動( 移動距離等於 0 )。求最多可以採集多少寶石。
解法：
考慮究竟有多少移動長度是會被用上的。試著每次都 +1 不斷疊上去，便會發現最多只會到約 +250。因此，實際上會用到的最後移動距離最多只有約 500 種( 因為還有負的要考慮 )。因此可以考慮動態規劃。
dp[ i ][ j ] : 目前在 i 號島，且最後一次移動距離為 j - D + 250，從這裡開始計算，未來可能的最大採集寶石數。
dp[ i ][ j ] = val[ i ] + max{ dp[ i + j - 1 ][ j - 1 ], dp[ i + j ][ j ], dp[ i + j + 1 ][ j + 1 ] }
狀態只需要開 O( N * sqrt( N ) ) = 30000 * 250。
於是我試著用 unordered_map，發現這東西還真慢。。。怎樣都不給過呢。

int N, D;
vi P;

void init(){
    cin >> N >> D;
    P = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> P[ i ];
}

vi cnt;

/*
struct hashfunc {
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
        return hash<T>()(x.first) ^ hash<U>()(x.second);
    }
};

unordered_map< pii, int, hashfunc > dp;
*/

int dp[ 30001 ][ 500 + 5 ];

int dfs( int u, int l ){
    if( not ( 0 < l and u <= 30000 ) )
        return 0;
    if( ~dp[ u ][ l - D + 250 ] )
        return dp[ u ][ l - D + 250 ];
    return dp[ u ][ l - D + 250 ] = cnt[ u ] + max( { dfs( u + l - 1, l - 1 ), dfs( u + l, l ), dfs( u + l + 1, l + 1 ) } );
}

void preprocess(){
    cnt = vi( 30000 + 1 );
    for( int i = 0; i < N; ++i )
        ++cnt[ P[ i ] ];
    memset( dp, -1, sizeof( dp ) );
}

void solve(){
    cout << dfs( D, D ) << endl;
}