読者です 読者をやめる 読者になる 読者になる

AOJ0145 Cards

解法
重ねあわせた全体のカードの束から、2つに分ける位置を決めるように区間DPする。
元のカード束のうち2つの隣接する束を重ねるという動作を最も原子的なものとして、同様のアルゴリズムが最後まで展開されることを汲み取れれば解ける。

反省
問題文を読まないといけない(戒め)

ll cfront[100], cback[100];
ll memo[101][101];

ll dfs(int l, int r) {
  
  if(memo[l][r]) return memo[l][r];
  if(l+1 == r) return 0;
  
  ll ret = INF;
  REP(m, l+1, r) {
    ret = min(ret, dfs(l, m) + dfs(m, r)
              + cfront[l]*cback[m-1]*cfront[m]*cback[r-1]);
  }
  
  return memo[l][r] = ret;
}

int main() {
  int N; cin >> N;
  rep(i, N)
    cin >> cfront[i] >> cback[i];
  cout << dfs(0, N) << endl;
  
  return 0;
}