随笔档案

第一题

该题主要考察了树形动归。根本原型是个背包。
定义状态f[i][j]为第i个节点给实际j时间（减去路上的消耗）所能偷得的画数。
方程可以轻易得出：f[i][j]=max(f[k][l],f[k][j-l])(k为i的儿子节点）

第二题

该题同样是树形动态规划。
定义状态f[i][0]为第i点不放士兵的最优解
f[i][1]为第i点放士兵的最优解
则
f[i][0]=sum(f[k][1])
f[i][1]=sum(min(f[k][0],f[k][1]))
这题就Over了。

本次作业的完整代码会在4月10日以后贴上来。