$2$ 人を人 $A,B$ とし、一番左の $1$ ミリメートルの部分を人 $A$ が取るとします。このとき、以下のようなDPを考えることができます。

$dp[i][j][k] :=$ 左から $i$ ミリメートルのみを考慮したとき、 $A$ が $B$ より $j$ ミリメートル多くとっていて、かつ $k=0$ なら一番右の $1$ ミリメートルの部分は $A$ のもの、 $k=1$ なら $B$ のものとなるような切り方で、その時点までの時間が最小となるもの

このとき、初期値と遷移は以下のようになります。 $2$ 行目と $3$ 行目は切らない場合の遷移、 $4$ 行目は切る場合の遷移です。

• $dp[0][0][0] = 0$
• $dp[i+1][j+1][k]=\min(dp[i+1][j+1][k],dp[i][j][k])$ $(k=0)$
• $dp[i+1][j-1][k]=\min(dp[i+1][j-1][k],dp[i][j][k])$ $(k=1)$
• $dp[i+1][j-1][1-k]=\min(dp[i+1][j-1][1-k],dp[i][j][k]+t_i)$

そのまま書くと $j$ の値がマイナスとなることがあり、言語によっては実行時エラーなどになるので、実装の際には $j$ に $N$ を足すなどして工夫するといいでしょう。

よって、このDPは \(O(N^2)\) で解くことができます。メモリ制限はDPテーブルとして配列を \(2\) つ用意し、交互に更新を行うことで削減でき、実行時間の定数倍は更新において参照する \(j\) の値を徐々に増やすなどをすることで改善できます。