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;
}