0w1

CFR 478 D. Red-Green Towers ( Rolling DP )

Problem - 478D - Codeforces

題意:
給兩種顏色方塊分別的數量,疊一座塔。塔的每一層顏色都必須相同,且頂層塊數為 1,每一層都必須比上面一層多恰一個方塊。求疊高度最高的塔的方案數。

數據範圍:
r: 紅方塊數量, g: 綠方塊數量, 0 ≤ r, g ≤ 2e5, 1 ≤ r + g

解法:
dp[ i ][ j ] : 已從上面疊 i 層,剩下 j 個綠方塊,此時的方案數。
只要有已疊高度和綠方塊剩量,就能確定紅方塊剩量。轉移部分顯然常數時間。
由於記憶體限制,層數用滾動陣列壓記憶體。若當前層無發生轉移則立即結束動態規劃程序。

時間 / 空間複雜度:
O( max( R, G ) ^ 1.5 ) / O( max( R, G ) )

int R, G;

void init(){
    cin >> R >> G;
}

vvi dp;
int ans;

void preprocess(){
    int maxh = sqrt( R + G << 1 );
    dp = vvi( 2, vi( R + 1 ) );
    dp[ 0 ][ R ] = 1;
    for( int i = 0; i < maxh; ++i ){
        int pass = 0;
        for( int r = 0; r <= R; ++r ) if( dp[ 0 ][ r ] ){
            int used = i * ( i + 1 ) / 2;
            int g = R + G - r - used;
            if( g >= i + 1 )
                pass = 1,
                ( dp[ 1 ][ r ] += dp[ 0 ][ r ] ) %= MOD7;
            if( r >= i + 1 )
                pass = 1,
                ( dp[ 1 ][ r - ( i + 1 ) ] += dp[ 0 ][ r ] ) %= MOD7;
        }
        if( not pass )
            break;
        swap( dp[ 0 ], dp[ 1 ] );
        fill( dp[ 1 ].begin(), dp[ 1 ].end(), 0 );
    }
}

void solve(){
    int ans = 0;
    for( int i = 0; i <= R; ++i )
        ( ans += dp[ 0 ][ i ] ) %= MOD7;
    cout << ans << endl;
}