好吧这次换比较正常的传送门嘤嘤嘤
首先感叹一下这居然是06年TG第一题！！感觉我的信心受到了暴击好伐。。。
那么作为区间dp的近乎模板题，且n的值也不大，所以三重循环完全可以A掉这道题，那么第一重循环区间的长度l，第二重循环区间开始的下标i，由这两重循环，我们可以求出区间结束的下标j=i+l，而第三重则循环由i到j-1的每一个下标k，状态转移方程则为dp[i][j]=ma(dp[i][k]+dp[k+1][j]+a[i]a[k+1]a[j+1],dp[i][j])
那么还有一点需要注意的是，由于这道题的题目说了这是一个环，so我们需要将原序列又n个值扩充至2n个值，输出时则寻找的dp[i][i+n]中的最大值

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 int n,ans;
 9 int a[305],dp[305][305];
10 
11 int ma(int a,int b){
   return a>b?a:b;}
12 int mi(int a,int b){
   return a<b?a:b;}
13 
14 int main(){
15     scanf("%d",&n);
16     for(int i=1;i<=n;i++){
17         scanf("%d",&a[i]);
18         a[i+n]=a[i];
19     }
20     for(int l=1;l<n;l++){
21         for(int i=1,j=i+l;i<n+n&&j<n+n;i++,j=i+l){
22             for(int k=i;k<j;k++){
23                 dp[i][j]=ma(dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1],dp[i][j]);
24             }
25         }
26     }
27     for(int i=1;i<=n;i++){
28         ans=ma(ans,dp[i][n+i-1]);
29     }
30     printf("%d\n",ans);
31     return 0;
32 }

嗯就是酱紫，应该还是比较好理解的and

新人开博鼓励一下吧。。

转载于:https://www.cnblogs.com/hahaha2124652975/p/11123249.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95733690

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。