额，我不想说什么了，这道题 区间DP 或者 记忆化搜索 都可以做出来，结果当时就没去做，
额，可能就是胆识不太够，不敢强打一波。
后来还是感觉自己对DP的理解不够有力道深度，索性总结了一下DP这就是DP，算是姊妹篇吧。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[105]; ll f[105][105]; ll dfs(int l,int r) { if(f[l][r]!=-1) return f[l][r]; if(l>=r) return 0; ll mn=0x3f3f3f3f; for(int i=l;i<=r;i++) { mn=min(mn,a[i]*(r-l)+dfs(l,i-1)+dfs(i+1,r)); } return f[l][r]=mn; } int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { memset(f,-1,sizeof(f)); int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cout<<dfs(1,n)<<endl; } }没记忆化的话就认头超时TLM呗。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[105]; ll f[105][105]; ll dfs(int l,int r) { //if(f[l][r]!=-1) return f[l][r]; if(l>=r) return 0; ll mn=0x3f3f3f3f; for(int i=l;i<=r;i++) { mn=min(mn,a[i]*(r-l)+dfs(l,i-1)+dfs(i+1,r)); } return mn; } int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { memset(f,-1,sizeof(f)); int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cout<<dfs(1,n)<<endl; } }区间DP的话
#include<bits/stdc++.h> #define inff 0x3f3f3f3f using namespace std; const int maxn=105; int dp[maxn][maxn]; int a[maxn]; int main() { int t,n; cin>>t; while(t--) { cin>>n; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dp[i][j]=inff; for(int len=1;len<=n;len++) for(int i=1;i+len-1<=n;i++) { //i为区间起点，j为区间终点，len-1为区间长度； int j=i+len-1; for(int k=i;k<=j;k++) //k在每个区间里面； dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+(len-1)*a[k]); } cout<<dp[1][n]<<endl; } }其实记忆化搜索就==DP，只不过一个是用dfs遍历寻找的最优子结构，一个是拿for循环的形式来找最优子结构。
说白了都是扫一遍dfs
其实不拿记忆化扫的话也能扫出整个的DP过程，但是会因为 dfs递归量太大爆掉
