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

AOJ 0145 Cards

問題

Cards

解法

dpでしょうか。lからrまでを重ねるための最小コストは(l<=i<r)、lからiまでとi+1からrまでのコストにlからiまでの塊とi+1からrまでの塊を重ねるためのコストの最小値。

dp[l][r] = min(dp[l][r], dp[l][i] + dp[i+1][r] + a[l]b[i]a[i+1]*b[r])

コード

int dp[100][100], n, a[100], b[100];

int dfs(int l, int r){
   if(l == r) return 0;
  if(dp[l][r] >= 0) return dp[l][r];

  int res = INF;
  REP(i, l, r){
    res = min(res, dfs(l, i) + dfs(i+1, r) + a[l]*b[i]*a[i+1]*b[r]);
  }
  return dp[l][r] = res;
}

int main(){
  memset(dp, -1, sizeof(dp));
  scanf("%d", &n);
  rep(i, n) scanf("%d%d", a+i, b+i);
  printf("%d\n", dfs(0, n-1));
  return 0;
}

メモ化じゃなくてdpで実装するとどうなるのかな。