区间dp
并不困难,这一类问题我的思通常是这样的:
关注最终状态。
我注意到了,最终只会剩一个元素。那么我们可以枚举这最后剩的一个元素。
决定了最后剩的元素就帮助我们把整个区间化成了两个小区间了。
类似分治了。
下面就是愉快的区间dp了
#include<cstdio> #include<algorithm> using namespace std; const int inf = 1e9; int dp[110][110],a[110],n; int main(){ scanf("%d",&n); for (int i=1;i<=n;++i)scanf("%d",&a[i]); for (int i=1;i<=n;++i)for (int j=i+2;j<=n;++j)dp[i][j]=inf; for (int p=3;p<=n;++p) for (int i=1,j=i+p-1;j<=n;++i,++j) for (int k=i+1;k<j;++k) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[k]*a[i]*a[j]); printf("%d\n",dp[1][n]); }