好难啊！

石子归并+路径记录（递归求路径）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我就是0607，不就是几个破题么~~~~~~~~~锁什么锁啊

#include<iostream>//区间动态规划 伪树dp
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<memory>
#include<algorithm>
#include<string>
#include<climits>
#include<queue>
#include<vector>
#include<cstdlib>
#include<map>
using namespace std;
const int INF=99999999;
const int maxn=100;
int n;
int a[maxn]; //保存分数
int root[maxn][maxn]; //保存的是使dp[i][j]最大的k 也就是根节点
int dp[maxn][maxn]; //区间dp 保存从i,j通过中序遍历组合成的最大值 dp[i...j]=max{dp[i...k-1]+dp[k+1...j]+a[k]|i<=k<=j}
//就是左子树*右子树+a[i]的最大值 枚举根节点
int pre[maxn];
void PreOrderTraval(int i,int j)
{
if(root[i][j]==-1) return;
cout<<root[i][j]<<" ";
//cout<<a[root[i][j]]<<" ";
//if(root[i][j]-1)//左子树不为空
PreOrderTraval(i,root[i][j]-1);
//if(n-root[i][j])//右子树不为空
PreOrderTraval(root[i][j]+1,j);
}
int main()
{
memset(root,-1,sizeof(root));

cin>>n;
//初始化所有节点都为空
for(int i=0;i<=n+1;i++) //0,n+1 对应 树的左儿子和右儿子为空的情况
for(int j=0;j<=n+1;j++)
dp[i][j]=1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i][i]=a[i];
root[i][i]=i; //单片叶子
}
/*
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++) //不要从i开始计算 叶子节点等于他本身
for(int k=j;k>=i;k--)
{
if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+a[k])
{
dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k];
root[i][j]=k;
}
}
*/
for(int len=2;len<=n;len++) //区间为1的时候为叶子不用枚举 按长度枚举区间
{
for(int i=1;i<=n-len+1;i++) //枚举区间起点 1....n-len+1 这个点是最后一个能取len长度的点
{
int j=i+len-1;//以len长度为终点的j=i+len-1

for(int k=i;k<=j;k++) //正序逆序枚举都没有关系
if(dp[i][j]<dp[i][k-1]*dp[k+1][j]+a[k])
{
dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k];
root[i][j]=k;
}
}
}
cout<<dp[1][n]<<endl;
int r=root[1][n];
PreOrderTraval(1,n);
cout<<endl;
/*
for(int i=1;i<n;i++)
cout<<pre[i]<<" ";
cout<<pre[n]<<endl;
*/
return 0;
}

#include <algorithm>
#include <iostream>
#include<string.h>
#include <fstream>
#include <math.h>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define exp 1e-8
#define fi first
#define se second
#define ll long long
#define INF 0x3f3f3f3f
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define mm(a,b) memset(a,b,sizeof(a));
#define for1(a,b) for(int a=1;a<=b;a++)//1---(b)
#define rep(a,b,c) for(int a=b;a<=c;a++)//b---c
#define repp(a,b,c)for(int a=b;a>=c;a--)///
#define stl(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
using namespace std;
void bug(string m="here"){cout<<m<<endl;}
template<typename __ll> inline void READ(ll &m){ll x=0,f=1;char ch=getchar();while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}m=x*f;}
template<typename __ll>inline void read(__ll &m){READ(m);}
template<typename __ll>inline void read(ll &m,ll &a){READ(m);READ(a);}
template<typename __ll>inline void read(ll &m,ll &a,__ll &b){READ(m);READ(a);READ(b);}
template<typename __ll>inline void read(ll &m,ll &a,__ll &b,__ll &c){READ(m);READ(a);READ(b);READ(c);}
template<typename __ll>inline void read(ll &m,ll &a,__ll &b,__ll &c,__ll &d){READ(m);READ(a);READ(b);READ(c);read(d);}
template < class T > T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template < class T > T lcm(T a, T b) { return a / gcd(a, b) * b; }
template < class T > inline void rmin(T &a, const T &b) { if(a > b) a = b; }
template < class T > inline void rmax(T &a, const T &b) { if(a < b) a = b; }
template < class T > T pow(T a, T b) { T r = 1; while(b > 0) { if(b & 1) r = r * a; a = a * a; b /= 2; } return r; }
template < class T > T pow(T a, T b, T mod) { T r = 1; while(b > 0) { if(b & 1) r = r * a % mod; a = a * a % mod; b /= 2; } return r; }

int dp[40][40];//dp[i][j]:=这个区间最大值
int root[40][40];//root[i][j]:=这个区间的根
int n;
int dat[40];
void solve(int l,int r)
{
for(int i=l;i<=r;i++) //枚举根
{
if(i==l)
{
if(dp[l][r]<dp[i+1][r]+dat[i])
{
dp[l][r]=dp[i+1][r]+dat[i];
root[l][r]=i;
}
}
else if(i==r)
{
if(dp[l][r]<dp[l][i-1]+dat[i])
{
dp[l][r]=dp[l][i-1]+dat[i];
root[l][r]=i;
}
}
else
{
if(dp[l][r]<dp[l][i-1]*dp[i+1][r]+dat[i])
{
dp[l][r]=dp[l][i-1]*dp[i+1][r]+dat[i];
root[l][r]=i;
}
}
}
}
void dfs(int l,int r)
{
if(l>r)return ;
cout<<root[l][r]<<" ";
dfs(l,root[l][r]-1);
dfs(root[l][r]+1,r);
}
int main()
{
read(n);
for1(i,n)read(dat[i]);
for1(i,n)dp[i][i]=dat[i],root[i][i]=i;
for(int l=n-1;l>=1;l--)
for(int r=i+1;r<=n;r++)
solve(i,j);
cout<<dp[1][n]<<endl;
cout<<root[1][n]<<" ";
dfs(1,root[1][n]-1);
dfs(root[1][n]+1,n);
}