https://torus711.hatenablog.com/entry/20150212/1423746983

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13659&rd=16313

問題概要

　一列に連結された $N$ 個のショッピングカートがある．次の 2 種類の操作を繰り返し適用して，全てのカートをできるだけ早く消し去りたい．

それぞれの列を，より短い 2 つの列に（任意の位置で）分割する
それぞれの列から，カートを 1 つ除去する

　また，1 つの列を分割する操作は，全体で $K$ 回以下しか行えない．
　必要な操作回数の最小値を求めよ．
　 $N \leq 100, K \leq 100$

解法

　ある $N, K$ が与えられたとき，その $N, K$ に対する最適解を求める関数を $f( n, k )$ とします．
　任意の $n, k$ に対して $f( n, k )$ を求める方法について考えます．このときに取れる戦略は， $n$ 個のカートを全て 1 つずつ除去していくか，列を 2 つに分けるかのいずれかです．列を分割するときは，残りの分割回数もそれぞれの列にどれだけ割り振るかを決めなければなりません．従って，それぞれ必要な手数は

1 つずつ除去する -> $n$
列を分割する -> $1 + \max( f( a, x ), f( b, y ) )$ （ただし， $a + b = n, x + y + 1 = K$ ）

となります．2 つをまとめると， $f( n, k ) = min( n, 1 + \max( f( a, x ), f( b, y ) ) )$ であることが分かります．分割する際には分割後のそれぞれの長さと，分割回数の割り当てを総当りする必要があります．
　さて，任意の $n, k$ に対して，最適な戦略が 1 つ以上定まり， $f( n, k )$ の値が不変であることを利用すると， $f$ をメモ化することができます．状態数は $O( NK )$ であり，ある $f( n, k )$ の値を（メモによらず）求めるには $O( nk )$ 時間かかります．2 回目以降に呼び出された状態に対しては定数時間で答えが返るので， $O( N^2K^2 )$ 時間で問題を解くことができます．
　オーダーから見るとちょっと厳しめっぽいですが，訪れない状態もあるので 150 ms ぐらいで通りました．

コード

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )

int dp[ 128 ][ 128 ];

class CartInSupermarketEasy
{
public:
	int calc( int N, int K )
	{
		fill( AALL( dp, int ), -1 );
		return rec( N, K );
	}

	int rec( const int N, const int K )
	{
		if ( dp[N][K] != -1 )
		{
			return dp[N][K];
		}

		if ( !K )
		{
			return dp[N][K] = N;
		}

		int res = N;
		REP( i, 1, N )
		{
			REP( j, 0, K )
			{
				res = min( res, 1 + max( rec( i, j ), rec( N - i, K - 1 - j ) ) );
			}
		}
		return dp[N][K] = res;
	}
};