素直に思いつくのは、次のようなDPでしょう。

• \(dp[i][j] =\) 先頭 \(i+j\) ミリメートルを \(i\) ミリと \(j\) ミリに分けるのにかかる秒数の最小値 (左端から \(i+j\) ミリメートルの位置で切断されているものとする)

このDPは、状態数が \(O(N^2)\) 個で、一回の遷移に \(O(N)\) 時間かかるので、全体で \(O(N^3)\) 時間となって間に合いません。

ここで、\(dp[i][j]\) の値は、次の値のうち小さい方に \(t_{i+j}\) を足したものです。

• \(dp[k][j]\) \((0≦k<i)\) の最小値
• \(dp[i][k]\) \((0≦k<j)\) の最小値

前者と後者を \(O(1)\) で計算できれば、遷移が \(O(1)\) 時間になり、この問題を解くことができます。

それは可能です。
例えば、次の配列を新たに用意することで、これらの最小値を \(O(1)\) で計算することができます。

• \(dp1[i][j] = \min(dp[0][j],dp[1][j], ... ,dp[i][j])\)
• \(dp2[i][j] = \min(dp[i][0],dp[i][1], ... ,dp[i][j])\)

また、これらの配列の更新も同様に \(O(1)\) で行うことができるので、この問題が解けました。

実装上の注意として、\(N\) が最大で \(10000\) と大きいため、DPテーブルを \(O(N^2)\) 要素の配列としてそのまま持つと MLE になってしまう可能性があります。

これを解決するには、例えば次のような方法があります。

• \(dp1[i][j]\) を参照するときに、代わりに \(dp1[i\%2][j]\) を参照するようにする
• \(dp2[i][j]\) についても同様にする

これは、\(dp1[i][j]\) や \(dp2[i][j]\) を更新する際に、\(dp1[i-1][x]\) にアクセスすることはあっても \(dp1[i-2][x]\) や \(dp1[i-3][x]\) にアクセスすることはないことから正当性が導かれます。

DPのメモリを節約する他の手法については、こちらの記事が詳しいです。
LIS でも大活躍！ DP の配列使いまわしテクニックを特集 - Qiita