CFR 478 D. Red-Green Towers ( Rolling DP )
題意:
給兩種顏色方塊分別的數量,疊一座塔。塔的每一層顏色都必須相同,且頂層塊數為 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; }