中文题。。题意略
我们知道每次枚举最后合并哪两个。。
于是枚举中间节点k
我犯的错误是将转移方程写成了，dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+a[l]*a[k+1]*a[k+2])
然而我们知道，dp[l][k]的头和尾是(l,k+1),dp[k+1][r]的头和尾是(k+1,r+1)
我居然没分析出这一点。。困惑于如果[1,4]分成的一个子区间[2,3]，dp[2][3]=dp[2][2]+dp[3][3]+a[2]*a[3]*?
这里看成最后一次合并。。你是a[2]*a[3]*a[2]呢，还是a[2]*a[3]*a[3]*a[3+1]=(由题意)a[2]*a[3]*a[3+1],如果我们按照题意头尾分析
我在纠结把2,3看成递归地最后一次合并应该怎么看待，如果按我的理解一开始按位置来最后俩合并的是2,3那么这俩相邻。。所以一定是互相乘
但是实际上根本不存在2,3最后一次合并。。
那么问题就变成了最后剩下两个就一定该互相乘吗？按照题意来说不是的
比如说1,2,3,4,5,1,2,3,4,5
如果按照整个区间来算比如 (3,4,5) (1,2)则这个算法总是有效
但是
(2,3,4)
(2,2) (3,4)
显然在小区间。。我们任何时候都应该考虑往右扩展，此时a[2]*a[3]*a[2]是不对的。。因为(3,4)这一部分合并完后缀一定是5
那么会不会有一种情况导致5这个珠子已经没了呢。。不会的。。因为我们在划分的时候，你看一下上面的序列就明白
要么1,5被隔开。。要么按5,1的顺序连在一起。。合并完前缀不还是5..所以这种情况后缀一定存在。。不必担心。。
所以给我们的启示是。。按照题目的规则合并。。因为我们在小子区间的臆想不符合题意。。要按照头尾标号进行合并计算
然后处理环形我们都开大一倍空间。。然后我们取i,i+(n-1)区间中最大的情况就好了，
但是N<=100,我才开了105,多开一倍空间的话就是201！奇葩OJ给我报了WA而不是RE，真是NB。。以后一定要小心环忘记开大数组而WA
然而后来我注意到一个显然的事实。。在小区间里发生的一定不是整个区间的最后一次合并。。并且合并计算的条件不是递归的。。而是整体静态的
贴18ms的代码。。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; int n; int a[255]; int dp[255][255]; int dfs(int l,int r,int dep){ // printf("DFS (%d,%d) DEP%d ",l,r,dep); if(dp[l][r]!=-1) return dp[l][r]; if(l>=r) return dp[l][r]=0; int k,p=0; for(k=l;k<r;++k){ p=max(p,a[l]*a[k+1]*a[r+1]+dfs(l,k,dep+1)+dfs(k+1,r,dep+1));//合并到r，则r的右端是r+1,而不是k+2 } p=max(p,a[l]*a[r]*a[r+1]+dfs(l,r-1,dep+1)); // printf("DFS (%d,%d) DEP%d ANS%d ",l,r,dep,p); return dp[l][r]=p; } int main(){ scanf("%d",&n); int i; for(i=1;i<=n;++i){ scanf("%d",a+i); } for(i=n+1;i<=2*n;++i){ a[i]=a[i-n]; } int ans=0; memset(dp,-1,sizeof(dp)); dfs(1,2*n-1,0); for(i=1;i<=n;++i){ ans=max(ans,dp[i][i+n-1]); } printf("%d ",ans); return 0; }