AOJ 0145 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で実装するとどうなるのかな。