UVa-348, LiveArchive-5456, TJU-2118, ZOJ-1276 : Optimal Array Multiplication Sequence
問題概要
いわゆる連鎖行列積。復元もあり。
解法
[from, to)型のDPの典型例。
acceptされたコード
計算量O(N^3)。
#include <cstdio> #include <string> #include <cstring> using namespace std; typedef long long int64; const int MAX_N = 10; const int64 INF = 1LL<<60; int N; int64 xs[MAX_N], ys[MAX_N]; int64 memo[MAX_N+1][MAX_N+1]; bool visited[MAX_N+1][MAX_N+1]; int div[MAX_N+1][MAX_N+1]; bool init(){ scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%lld%lld", xs + i, ys + i); } memset(visited, false, sizeof(visited)); return N>0; } //[from, to) int64 rec(int from, int to){ if(visited[from][to]){ return memo[from][to]; } visited[from][to] = true; int64& ret = memo[from][to] = INF; if(to - from == 1){ return ret = 0; } for(int mid=from+1; mid<to; mid++){ int64 tmp = rec(from, mid) + rec(mid, to) + xs[from]*xs[mid]*ys[to-1]; if(tmp < ret){ ret = tmp; div[from][to] = mid; } } return ret; } string get(int n){ char buf[10]; sprintf(buf, "A%d", n); return string(buf); } string rec2(int from, int to){ if(to - from == 1){ return get(from+1); } string a = rec2(from, div[from][to]), b = rec2(div[from][to], to); return "(" + a + " x " + b + ")"; } void solve(){ rec(0, N); puts(rec2(0, N).c_str()); } int main(){ int c = 1; while(init()){ printf("Case %d: ", c++); solve(); } return 0; }