比较特别的区间dp。小的区间转移大的区间时，也要枚举断点。不过和普通的区间dp比，断点有特殊意义。表示断点是区间最后取走的点。而且一个区间表示两端都不取走时中间取走的最小花费。
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <iomanip> #include <cstring> #include <map> #include <queue> #include <set> #include <cassert> using namespace std; const double EPS=1e-8; const int SZ=220,INF=0x7FFFFFFF; typedef long long lon; int n,arr[220],dp[220][220]; void init() { cin>>n; for(int i=1;i<=n;++i)cin>>arr[i]; for(int i=1;i+2<=n;++i)dp[i][i+2]=arr[i]*arr[i+1]*arr[i+2]; for(int len=3+1;len<=n;++len) { for(int i=1;i<=n;++i) { int r=i+len-1; dp[i][r]=INF; for(int j=i+1;j+1<=r;++j) { dp[i][r]=min(dp[i][r],dp[i][j]+dp[j][r]+arr[j]*arr[i]*arr[r]); } } } cout<<dp[1][n]<<endl; } int main() { std::ios::sync_with_stdio(0); //freopen("d:\\1.txt","r",stdin); //lon casenum; //cin>>casenum; //for(lon time=1;time<=casenum;++time) //for(lon time=1;;++time) { init(); //work(); } return 0; }
原文：https://www.cnblogs.com/gaudar/p/9733291.html