区间dp
题目在最后
`#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
i
- List item
nt a[maxn];
int dp[maxn][maxn];
int main(){
int t,n,j=1;
cin>>t;
while(t–){
cin>>n;
memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
cin>>a[i];
for(int len=3;len<=n;len++)
for(int i=1;i+len-1<=n;i++){
int r=i+len-1;
for(int k=i+1;k<r;k++)
dp[i][r]=max(dp[i][r],dp[i][k]+dp[k][r]+a[i]*a[k]*a[r]);
} cout<<“Case #”<<j++<<": "<<dp[1][n]<<endl;
}
return 0;
}`