1651 Multiplication Puzzle

問題概要

n枚の数字の書かれたカードが一列に並んでいる。
これを使って以下のようなゲームをする。

• 両端以外のカードを一枚選び、そのカードと、その両隣のカードの数字3つを掛けた数をスコアに足す
• そのカードを取り除く
• この操作を残りのカードが2枚になるまで繰り返す

このとき、スコアの最小値を求めよ。

解法

dp[i][j]をi枚目からj枚目までのカードのうち、両端を残して間を全て取り除くのに必要な最小のスコアとすると、
dp[i][j]=min{dp[i][k]+dp[k][j]+(i,k,jの数字の積)}となる。

この漸化式を使うことでO(n^3)のDPができる。

ソースコード

int n,c[100];
int dp[100][100];

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d",c+i);
	rep(i,n)rep(j,n)dp[i][j]=inf;
	rep(i,n-1)dp[i][i+1]=0;
	
	for(int len=3;len<=n;len++)rep(l,n-len+1)
	{
		int r=l+len-1;
		for(int m=l+1;m<r;m++)dp[l][r]=min(dp[l][r],dp[l][m]+dp[m][r]+c[l]*c[m]*c[r]);
	}
	printf("%d\n",dp[0][n-1]);
	
	return 0;
}