Halloween Costumes (UVa Live Archive Asia - Site 9 (Bangladesh) - 2010/2011 Dhaka (Bangladesh))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4857

問題

[1,m]の整数で表現される長さnの数列がある。普通のstackでpush,pop,topを使って与えられた数列を再現することにする。最低何回のpushが必要か？
1<=n,m<=100

解法

DPで解く。dp[use][left][right]は[left,right)間の数列を再現するために必要な最低のpush回数-useを返す(useは0か1)。leftと同じ数値の場所をindexとすると、
dp[use][left][right]=min(dp[0][left + 1][index] + dp[1][index][right]) + 1 - use
となる。計算量はO(n^3)。