目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。

大多数动规都是在一维二维这种规则的背景下的，可以解决的问题比较局限，而树作为一种特殊的图，可以描述比较复杂的关系，再加上树的递归定义，是一种非常合适动规的框架，树型动态规划就成为动规中很特殊的一种类型。

树形动态规划典型例题

没有上司的晚会

【问题描述】

有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。

已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

【输入：】

第1行一个整数

接下来

接下来每行两个整数

输入以0 0结束。

【输出】：

一个数，最大的气氛值和。

【样例输入】

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

0 0

树形动态规划样例输出

5

【分析】

如上例，上司与小兵之间的关系构成一棵树。

5

| \

3 4

| \ | \

1 2 6 7

又是求最优解，并且每一个节点的取舍关乎到全局 因此，此题可用树形动态规划

我们可用

C ：

#include
 
  
using namespace std;
int main()
{
intn,qf[201],f[201][2],shs[201],xb[201][201],shu[201][201],x,s,maxc,j,k,a,b,l,i;//qf存储每个人的气氛值，shs存储每个人的上司，xb存储每个人的下属，shu存储构成的树,maxc存储最大层数
cin>>n;
for(i=0;i<=n;i  )
{
xb[i][0]=0;
shs[i]=0;
}
for(i=1;i<=n;i  )cin>>qf[i];
l=1;
k=1;
while(l!=0||k!=0)
{
cin>>l>>k;
shs[l]=k;
xb[k][0]  ;
xb[k][xb[k][0]]=l;
}
maxc=0;
for(i=1;i<=n;i  )
{
x=i;
s=1;
while(shs[x]!=0)
{
x=shs[x];
s=s 1;
}
shu[s][0]  ;
shu[s][shu[s][0]]=i;
if(s>maxc)maxc=s;
}//建树,maxc存储最大层数
for(i=maxc;i>=1;i--)
for(j=1;j<=shu[i][0];j  )
{
if(xb[shu[i][j]][0]==0)
{
f[shu[i][j]][0]=0;
f[shu[i][j]][1]=qf[shu[i][j]];
}
else
{
f[shu[i][j]][0]=0;
f[shu[i][j]][1]=qf[shu[i][j]];
for(k=1;k<=xb[shu[i][j]][0];k  )
{
a=f[xb[shu[i][j]][k]][0];
b=f[xb[shu[i][j]][k]][1];
f[shu[i][j]][1] =a;
if(b>a)a=b;
f[shu[i][j]][0] =a;
}//动态转移方程
}
}
s=0;
for(i=1;i<=shu[1][0];i  )
{
a=f[shu[1][i]][0];
b=f[shu[1][i]][1];
if(a
   
   
大家看到，树形动态规划基本上可以分为2个部分，一个是建树，另一个就是动态规划，一个好的数据结构，能使你编程非常容易，这也是树形动态规划的难点之一 
   

   pascal：
   
type
link=^node;
node=record
s:longint;
next:link;
end;
constmaxn=100;
var
r:array[1..maxn]oflongint;{存储每个人的搞笑指数}
sum:array[1..maxn,0..1]oflongint;
son:array[1..maxn]oflink;{记录指向儿子结点的指针}
n,root:longint;
i,a,b:longint;
p:link;
functionmax(a,b:longint):longint;
beginifa>bthenexit(a)elseexit(b);end;
procedurecalc(k:longint);{k是根结点}
var
p:link;
i:longint;
begin
sum[k][0]:=0;{初值为0}
sum[k][1]:=0;
p:=son[k];{取结点k的孩子结点}
whilep<>nildo
begin
i:=p^.s;
calc(i);{递归调用此过程，计算以i为根结点的最大搞笑指数}
inc(sum[k][0],max(sum[i][0],sum[i][1]));
inc(sum[k][1],sum[i][0]);
p:=p^.next;{算兄弟}
end;
inc(sum[k][1],r[k]);
end;
begin
read(n);
fori:=1tondo{读入每个结点的搞笑指数}
read(r[i]);
fori:=1ton-1do{n个结点的相互连通的树共有n-1条边}
begin
read(a,b);{b是a的上级}
inc(root,a);{对儿子结点的编号求和}
new(p);{以孩子兄弟表示法来存储树的结构}
p^.s:=a;
p^.next:=son[b];{数组son的初值应为nil}
son[b]:=p;
end;
root:=(n*(n 1)div2)-root;{计算出根结点的编号}
calc(root);
writeln(max(sum[root][0],sum[root][1]));
end.
2100433B
  
 

动态规划就是解决多阶段决策最优化问题的一种思想方法。

树形动态规划阶段

将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。

树形动态规划状态

各阶段开始时的客观条件叫做状态。

树形动态规划决策

当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。

树形动态规划策略

由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。

树形动态规划状态转移方程

前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k 1阶段状态的演变规律，称为状态转移方程。

水资源系统动态规划水资源规划

水资源规划即在掌握水资源的时空分布特征、地区条件、国民经济对水资源需求的基础上，协调各种矛盾，对水资源进行统筹安排，制定出最佳开发利用方案及相应的工程措施的规划。它是水资源管理的一个重要部分。

水资源系统动态规划动态规划

动态规划是用以求解多阶段决策过程最优化策略问题的方法。其基本思路是将一个复杂的系统分析问题分解为一个多阶段的决策过程，并按一定顺序或时序从第一阶段开始，逐次求出每阶段的最优决策，经历各阶段而求得整个系统的最优策略。

水利规划中的许多问题，如水资源优化分配、工程布局和规模优化、工程最优开发顺序等都可用其求解。为了克服方法存在的“维数障碍”，曾提出过许多改进途径，如在确定性动态规划方而的状态增量动态规划法、离散微分动态规划法、微分动态规划法、逐次逼近法、逐次优化算法(POA)和在随机动态规划方而的参数迭代法等。中国学者提出了一种状态极值逐次优化算法(SEPOA)和多维动态规划试验选优法等，使高维动态规划问题的求解成为可能。动态规划应用于水利规划时存在的另一障碍，是研究对象中的状态往往存在后效性。例如在海涂促淤围垦优化规划中，促淤决策影响着围垦决策，围垦决策也影响着促淤决策；在除涝排水系统规划中，作为状态变量的河网规模与排水闸尺寸也是相互制约的。针对这两种情况，中国已分别提出了试误迭代法和建立河网规模与排水闸尺寸的关系方程作为约束条件来加以克服，从而扩大了动态规划的应用范围。在随机动态规划方面，也提出过一些多维随机动态规划算法和多目标随机动态规划算法等，均有所创新。

水资源系统规划是水资源合理开发利用的有效途径。随着全球社会经济的发展，水资源在经济可持续发展中具有基础性地位和至关重要的作用。为了合理利用水资源，实现水资源可持续利用，保障经济社会可持续发展，我们需要对水资源进行合理规划，研究水资源规划方法。近年来，对水资源规划方法的研究不断加深,并取得了大量成果。动态规划模型在越来越多的应用在水资源规划中，具有将高维问题化为相对简单的低维问题、对目标函数和约束条件的函数形式限制较宽、处理比较方便等优点。以经济、社会、环境综合效益最大为目标，通过分析水资源现状，建立动态规划模型，能够有效的了解水资源供需矛盾。

我局召开督察员工作交接见面座谈会

2013年3月6日下午，衡水市城乡规划局召开了省住建厅派驻衡水城乡规划督察员工作交接见面座谈会。省建设监察办副主任吴清波、省建设监察办规划督察科科长邢光明、省住建厅派驻衡水原督察员王英麒和新任督察员张胜军及衡水市政府副秘书长张奎元、市城乡规划局党组全体成员、局机关各科室科长参加了会议。

交接仪式上，省建设监察办吴清波副主任介绍了我省城乡规划督察工作的开展情况，充分肯定了原督察员王英麒同志多年的驻衡工作，介绍了新任督察员张胜军的有关情况，重申了督察员职责，提出了督察工作要求，希望衡水的城乡规划工作更加规范，城市建设更上一台阶。原省住建厅驻衡督察员王英麒、现省住建厅驻衡督察员张胜军均作了表态发言。

市政府副秘书长张奎元代表市政府欢迎新督察员的到来，并感谢了原督察员对衡水规划工作的帮助。表示一定会全力支持督察员工作，严格按照规划法及相关法律、法规做好规划工作。市城乡规划局局长张峰、副局长杨凝均表态：感谢省住建厅对衡水城乡规划工作的关心和重视，将全力配合驻衡督察员工作，进一步提升规划工作水平。

2100433B