poj1651

链接:poj1651

题解

• $$区间i~j可以划分为i~k k+1~j 答案加上nm[k]*nm[i-1]*nm[j]就好$$

  #include<iostream>
  #include<cstdio>
  #include<cmath>
  #include<cstdlib>
  #include<cstring>
  #include<algorithm>
  #define rep(i,x,y) for(register int i=x;i<=y;++i)
  #define repd(i,x,y) for(register int i=x;i>=y;--i)
  #define ll long long
  using namespace std;
  const int N=107;
  const ll inf=0x3f3f3f3f3f3f3f;
  ll dp[N][N],nm[N];
  int n;
  int main(){
  	scanf("%d",&n);
  	rep(i,1,n)scanf("%d",&nm[i]);
  	rep(l,2,n-1)rep(i,2,n-l+2){
  		int j=i+l-1;
  		dp[i][j]=inf;
  		rep(k,i,j-1)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+nm[k]*nm[i-1]*nm[j]);
  	}
  	printf("%lld\n",dp[2][n]);
  	return 0;
  }