Climber.pI的OI之路

Through the darkest dark,may we see the light.

NOIp 2003 加分二叉树

形DP,需要记录方案,并注意空树的情况.
[状态]f[i][j]从结点i到j的最大加分值
[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)

实现方程的时候循环顺序非常关键:结点数由小到大循环.否则会出现需要的值未计算的情况.
记录方案可以用一个数组d[i][j]记录k,然后递归寻找方案并记录.

 1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 int f[35][35] = {0}, d[35][35] = {0}, ans[35] = {0}, t = 0;
 5 void print(int start, int end){
 6     if (start > end) return;
 7     if (start == end) {ans[++t] = start; return;}
 8     ans[++t] = d[start][end];
 9     print(start, d[start][end]-1);
10     print(d[start][end]+1, end);
11 }
12 int main(){
13     int n, a[35] = {0}, i, j, k, l;
14     scanf("%d", &n);
15     for (i = 1; i <= n; i++){
16         scanf("%d", &a[i]);
17         f[i][i-1] = 1;
18         f[i][i] = a[i];
19     }
20     for (l = 2; l <= n; l++)
21         for (i = 1; i <= n; i++)
22             for (k = i; k <= i+l-1; k++){
23                 j = i+l-1;
24                 if (f[i][j] < f[i][k-1]*f[k+1][j] + a[k]){
25                     f[i][j] = f[i][k-1]*f[k+1][j] + a[k];
26                     d[i][j] = k;
27                 }
28             }
29     printf("%d\n", f[1][n]);
30     print(1, n);
31     for (i = 1; i < t; i++) printf("%d ", ans[i]);
32     printf("%d\n", ans[t]);
33 }
34 


posted on 2010-10-05 11:10 Climber.pI 阅读(999) 评论(4)  编辑 收藏 引用 所属分类: 动态规划

Feedback

# re: NOIP 2003 加分二叉树 2010-10-05 11:30 dementrock

担心未计算用记忆化搜索就行了..  回复  更多评论   

# re: NOIP 2003 加分二叉树 2010-10-06 09:30 Climber.pI

调试的时候发现有未计算的情况,然后联想起usaco里以前看到的某种方法..  回复  更多评论   

# re: NOIP 2003 加分二叉树 2010-10-06 10:31 dementrock

记忆化搜索是不可能有未计算的……只可能写猥了  回复  更多评论   

# re: NOIp 2003 加分二叉树 2010-10-08 21:57 Climber.pI

@dementrock
不会爆栈么?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理