E - Multiplication Puzzle
POJ - 1651 题意：不断取数最后留下第一个跟第n个取数话费为这个数a[i]*a[i-1]*a[i+1]求怎么取最小话费。思路：区间dp从小区更新到大区间维护最小值。老套路① 区间长度②枚举起点③枚举中间点 #include<iostream>
#include<cstring>
using namespace std;
#define maxn 111
#define ll long long
#define inf 0x3f3f3f3f
int n,a[maxn];
int dp[maxn][maxn];
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
for(int len=2; len<n; len++)
for(int i=1; i+len<=n; i++)
{
int j=i+len;
dp[i][j]=inf;
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]);
}
cout<<dp[1][n]<<endl;
return 0;
}
