PKU 1651-Multiplication Puzzle

問題概要

眠いので略

解法

メモ化再帰．
区間[s,e)の最適解を求めるということを繰り返す．
詳しくはソースを

実装(C++)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int cards[100];
long long dp[101][101];
long long solve(int s,int e){
	if(e<=s)return 0;
	if(dp[s][e]>=0)return dp[s][e];
	long long ans=9999999999999999LL;
	for(int i=s;i<e;i++){
		ans=min(ans,cards[s-1]*cards[e]*cards[i]+solve(s,i)+solve(i+1,e));
	}
	return dp[s][e]=ans;
}
int main() {
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>cards[i];
	memset(dp,-1,sizeof(dp));
	cout<<solve(1,n-1)<<endl;
	return 0;
}