n个小球从二维的天空下落。你在(x0,0)处且只能横向移动，速度1单位距离/秒。每个小球从(xi, yi)处以vi速度下落。
每个小球接到的价值为 当前的y / 1000，（可能为负值）
求接住每个小球的最大价值和。（可能为负）
区间dp。
引自论文：
在常规动态规划问题中，我们面临当前状态时**“行动”** 造成的花费往往与这个状态是 同时计算 的 。
本题中，当前“行动”费用的一部分需要在之前决策时被计算并以状态的形式对当前状态造成影响。造成这 一独特的计算的原因就是当前的决策会对未来的“行动”费用造成影响。这类问题 构造方程往往比较困难，需要仔细分析原题，找到矛盾所在。
那么简单来说就是现在的决策内容会对之后的计算价值产生影响。
该题中，射击的得分与当前的时刻相关。但当前的时刻是不能由上一个状态表示出来。
矛盾在于曾经花费的时间对当前状态造成了影响。
怎么办？我们在每次移动（决策）时，将该决策对未来的影响计算出来就可以了。也就是计算出决策使未来减少的得分。
故可以定义f[i][j][1/0]表示接住 [i,j]的小球且最后停在 i或j时 损失掉的价值。（其实也可以定义成总价值，区别不大）
代码
一颗点数为n 的树，选择k个点染成黑色，其余点染成白色。
收益为：黑点两两之间的距离 + 白点两两之间的距离。求最大收益
每一条边的贡献就是这条边两边的（黑点数相乘 + 白点数相乘）* 边权，
因此定义 f[i][j]表示以i为根的子树中，选了j个黑点对答案的贡献是多少。
转移时针对一条边转移，枚举这个子树中选的黑点数，做树形背包dp即可。
代码
n个点的树放m个监听设备。每个设备能监听所有相邻节点但不能监听自身。
求恰好放完m个设备，保证每个节点都能被监听到的方案数
树形背包的经典转移：f[u][i+j]=combine(f[u][i],f[v][j])
设状态为：f[u][j][0/1][0/1] ，以u为根的子树，选了j个点，u选/不选，u是否被覆盖。
- f[u][i+j][0][0]=∑f[u][i][0][0]∗f[v][j][0][1]
- f[u][i+j][1][0]=∑f[u][i][1][0]∗f[v][j][0][1/0]
- f[u][i+j][0][1]=∑f[u][i][0][1]∗f[v][j][1/0][1]+f[u][i][0][0]∗f[v][j][1][1]
- f[u][i+j][1][1]=∑f[u][i][1][1]∗f[v][j][1/0][1/0]+f[u][i][1][0]∗f[v][j][1][1/0]
然后因为是计数问题，我们无法排除 i=i+j 的情况。故对于每个f[u][i]，我们开一个新数组存储并将f[u][i]清零，然后采取刷表法更新答案。
注意该题中 long long 开不下这么大的数组。所以用int开，中间变量用long long更新。注意细节处不要爆long long (T T)
代码