PKU 1651 Multiplication Puzzle

1651 -- Multiplication Puzzle

[問題]
N枚のカードが与えられる。これらの中から任意の1枚を取り除く。この際、選んだカード * 左のカード * 右のカードのスコアが加算される。ただし両端のカードは選べない。 可能な限りこれらの操作を繰り返した時の合計スコアを最小化せよ。

[解法]
dpをするにもカードの現在の状態をどう保持すれば良いかわからず、ずっと悩んでいた。(このNの制約ではビットdpは不可能)
いろいろ調べたところ、どうやら区間dpで解けるらしい。区間[a,b]から任意のカードxを取り除くということは、考える区間が[a,x),(x,b]の半開区間になるということになる。　なので、dp[a][b] = [a,b)における最小スコア　を計算すれば良い。

持たせるデータの工夫という面で、すごく勉強になりました。

まだまだ奥が深いですねっ！

ll dp[101][101];
int card[100];
int N;
ll dfs(int a,int b){
  if(a >= b) return 0;
  if(dp[a][b] >= 0) return dp[a][b];
  ll ans = 999999999LL;
  for(int x = a; x < b; x++)
    ans = min(ans,card[a - 1] * card[x] * card[b] + dfs(a,x) + dfs(x + 1,b));
  
  return dp[a][b] = ans;
}
int main(){
  cin>>N;
  rep(i,N) cin>>card[i];
  memset(dp,-1,sizeof(dp));
  cout<<dfs(1,N - 1)<<endl;
  
}