问题简述
有一棵Treap，每个节点有一个互不相同的数据值和权值，以及一个访问频度。一个节点的访问代价为它的访问频度乘以它在树中的深度，整棵树的访问代价定义为所有节点的访问代价之和。节点的权值可以修改为任意实数，每修改一个节点的权值的代价为K。任务是修改一些节点的权值，使得整棵树的访问代价与修改代价之和最小。
问题建模
首先离散化所有节点的权值，对所有节点按照数据值排序后线性存储。定义S[i,j]为(排序后)第i个节点到第j个节点的访问频度之和。
解法 动态规划
算法描述
定义Weight[i]为状态转移方程为第i个节点离散化后的权值，F[i,j,w]表示从第i个节点到第j个节点组成一棵子树的最小代价，子树根节点的权值≥w。状态转移方程为
边界条件为
，目标函数为
。
算法分析
对于一个状态F[i,j,w]，我们要枚举从节点[i..j]组成的这棵子树的根节点k，其左子树为[i..k-1]，右子树为[k+1..j]。如果根节点k的权值Weight[k]≥w，那么节点k的权值无需修改即可直接作为该子树的根节点。总代价为左子树的代价F[i,k-1, Weight[k]]，加上右子树的代价F[k+1,j, Weight[k]]，以及整个子树的访问频度之和。
另外一种情况，修改节点k的权值，使之不小于w。由于我们已经离散化了权值，修改后的权值不应是整数，以免和已有重复。假设节点k修改后的权值为w加上一个很小的小数，其左右子树根节点的权值都不应小于节点k修改后的权值。我们约定如果根和子节点都必须大于w的话，则子节点的权值比根节点略大，且大于w。于是这种情况的总代价为左子树的代价F[i,k-1, w]，加上右子树的代价F[k+1,j, w]，加上修改权值的代价K，以及整个子树的访问频度之和。
复杂度分析
状态数为O(N3)，每次转移需要以O(N)的时间枚举k，所以时间复杂度为O(N4)。在实际测试中通过了所以测试点，得到100分。参考程序
```cpp /* * Problem: NOI2009 treapmod * Author: Guo Jiabao * Time: 2009.9.24 14:50 * State: Solved * Memo: 动态规划 */ #includetypedef long long big;
const int MAXN = 72; const big INF = ~0ULL»1;
struct node { int val,wei,freq; }P[MAXN];
int N,K; big sf[MAXN],F[MAXN][MAXN][MAXN],Ans=INF;
void init() { int i; freopen(“treapmod.in”,“r”,stdin); freopen(“treapmod.out”,“w”,stdout); scanf("%d%d",&N,&K); for (i=1;i<=N;i++) scanf("%d",&P[i].val); for (i=1;i<=N;i++) scanf("%d",&P[i].wei); for (i=1;i<=N;i++) scanf("%d",&P[i].freq); memset(F,-1,sizeof(F)); }
inline int cmp1(const void *a,const void *b) { return ((node *)a) -> wei - ((node *)b) -> wei; }
inline int cmp2(const void *a,const void *b) { return ((node *)a) -> val - ((node *)b) -> val; }
inline big sum(int i,int j) { return sf[j] - sf[i-1]; }
big dp(int i,int j,int w) { if (i>j) return 0; if (F[i][j][w] == -1) { int a; big t,rs=INF; for (a=i;a<=j;a++) { t = dp(i,a-1,w) + dp(a+1,j,w) + sum(i,j) + K; if (t < rs) rs = t; if (P[a].wei >= w) { t = dp(i,a-1,P[a].wei) + dp(a+1,j,P[a].wei) + sum(i,j); if (t < rs) rs = t; } } F[i][j][w] = rs; } return F[i][j][w]; }
void solve() { int i; qsort(P+1,N,sizeof(P[0]),cmp1); for (i=1;i<=N;i++) P[i].wei = i; qsort(P+1,N,sizeof(P[0]),cmp2); for (i=1;i<=N;i++) { P[i].val = i; sf[i] = sf[i-1] + P[i].freq; } for (i=0;i<=1;i++) { big t = dp(1,N,i); if (t < Ans) Ans = t; } }
int main() { init(); solve(); cout « Ans « endl; return 0; }
上次修改时间 2017-05-26