[poj] 1651 Multiplication Puzzle || 区间dp

原题

乘法游戏

---

f[i][j]表示i到j区间只有i和j剩余的最小值
f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]a[k]a[j])

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110
using namespace std;
int n,a[N],f[N][N];

int main()
{
    scanf("%d",&n);
    memset(f,127,sizeof(f));
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) f[i][i]=a[i],f[i][i+1]=0;
    for (int d=1;d<=n;d++)
	for (int i=1,j;i+d<=n;i++)
	{
	    j=i+d;
	    for (int k=i+1;k<j;k++)
		f[i][j]=min(f[i][j],f[i][k]+a[i]*a[k]*a[j]+f[k][j]);
	}
    printf("%d",f[1][n]);
    return 0;
}