自己的思维能力果然还是太不够……想到了这棵树所有的性质即中序遍历不变，却并没有想到怎样利用这一点。在想这道题的过程中走入了诸多的误区，在这里想记录一下 & 从中吸取到的教训（原该可以避免的吧）。
1. 注意到了中序遍历不变的性质却不会使用。
2. 注意到只有相对大小才会影响树的形态，在考虑的时候一直在想如何改变一个数的位置关系，分析修改权值对于树产生的影响。但这样是很难分析的，将树看作一个整体也不利于dp状态的划分。
3. 想不出怎样计算一个节点的深度（不能快速找到一个节点所处的位置）。
正确的思维应当是：
1.中序遍历不变 ---> 数值排名位于 [l, r] 这个区间中的所有树必然可能同在一棵子树中（且这棵子树中不含其他的节点）；
2.不好计算一个节点插入的深度 / 不好修改一个数在子树中的位置：改修改为插入。整棵子树中，唯一一个容易确定位置的节点：若这个节点是当前子树中权值最小的，则这个节点为子树的根，其余所有节点的深度 ++；
于是正确的 dp 状态就出来了。\(dp[l][r][v]\) 表示 \(l\) 到 \(r\) 的区间所有节点 \( >= v \) 的最小代价。转移方程分别为两种：修改该节点权值 & 不修改该节点权值。
\(dp[l][r][v] = dp[l][k - 1][v] + dp[k + 1][r][v] + K + sum[l][r];\)
\(dp[l][r][v] = dp[l][k - 1][P[i].v] + dp[k + 1][r][P[i].v] + sum[l][r];\)
其中，第二个转移方程中要求 \(P[i].v >= v\)，\(P[i].v\) 是节点原本的权值，\(sum[l][r]\) 为区间 \(l -> r\) 的访问频率。
#include <bits/stdc++.h>
using namespace std;
#define maxn 100
#define int long long
#define INF 999999999999LL
int n, K, sum[maxn];
int ans = INF, dp[maxn][maxn][maxn]; struct node
{
int num, v, w;
}P[maxn]; int read()
{
int x = , k = ;
char c;
c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} bool cmp(node a, node b) { return a.v < b.v; }
bool cmp1(node a, node b) { return a.num < b.num; }
void gmin(int &x, int y) { x = x < y ? x : y; } int dfs(int l, int r, int v)
{
if(~dp[l][r][v]) return dp[l][r][v];
else dp[l][r][v] = INF;
if(l > r) return dp[l][r][v] = ;
for(int k = l; k <= r; k ++)
{
gmin(dp[l][r][v], dfs(l, k - , v) + dfs(k + , r, v) + K + sum[r] - sum[l - ]);
if(P[k].v >= v) gmin(dp[l][r][v], dfs(l, k - , P[k].v) + dfs(k + , r, P[k].v) + sum[r] - sum[l - ]);
}
return dp[l][r][v];
} signed main()
{
n = read(), K = read();
memset(dp, -, sizeof(dp));
for(int i = ; i <= n; i ++) P[i].num = read();
for(int i = ; i <= n; i ++) P[i].v = read();
for(int i = ; i <= n; i ++) P[i].w = read();
sort(P + , P + + n, cmp);
for(int i = ; i <= n; i ++) P[i].v = i;
sort(P + , P + + n, cmp1);
for(int i = ; i <= n; i ++) sum[i] += sum[i - ] + P[i].w;
ans = min(ans, dfs(, n, ));
printf("%lld\n", ans);
return ;
}
2. 加分二叉树
双倍经验……
#include <bits/stdc++.h>
using namespace std;
#define maxn 40
#define int long long
int n, a[maxn];
int f[maxn][maxn], dp[maxn][maxn]; int read()
{
int x = , k = ;
char c;
c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} int dfs(int l, int r)
{
if(dp[l][r]) return dp[l][r];
if(l > r) return dp[l][r] = ;
if(l == r) return f[l][r] = l, dp[l][r] = a[l];
for(int k = l; k <= r; k ++)
{
int x = dfs(l, k - ), y = dfs(k + , r);
if(dp[l][r] < x * y + a[k])
{
dp[l][r] = x * y + a[k];
f[l][r] = k;
}
}
return dp[l][r];
} void Get_ans(int l, int r)
{
if(l > r) return;
printf("%lld ", f[l][r]);
Get_ans(l, f[l][r] - ), Get_ans(f[l][r] + , r);
} signed main()
{
n = read();
for(int i = ; i <= n; i ++) a[i] = read();
printf("%lld\n", dfs(, n));
Get_ans(, n); puts("");
return ;
}