【IOI2014】Friend
动态规划，思维题
题目大意：
有 $n$ 个人，编号为 $0\sim n-1$。现在要建立一个关系网。
一开始只有 $0$ 号在关系网内，现在要将 $1\sim n-1$ 号依次加入。
加入 $i$ 的时候，会选择一个 $0\sim i-1$ 的人当做主持人。然后有三种情况：
IAmYourFriend，$i$ 号将和他的主持人成为朋友。MyFriendsAreYourFriends，$i$ 号将和当前时刻他的主持人的朋友成为朋友（和主持人不成为朋友）。WeAreYourFriends，$i$ 号将和当前时刻他的主持人以及主持人的朋友成为朋友。
每个人有一个正的可信度。
现在要在最终的关系网中选择若干个人，满足两两之间都不是朋友。
求所有选法中，可信度之和的最大值。
题解：
很妙的题。
题目相当于求最终建出来的图的最大独立集。
对于每个点，我们将它的主持人看作它的父亲，那么所有点形成了一棵以 $0$ 为根的有根树。
树的最大独立集可以通过简单的 DP 得到，对于本题，也可以尝试自底向上地进行 DP。
定义 $p_i$ 表示 $i$ 的主持人编号。令 $f_i,g_i$ 分别表示对编号大于等于 $i$ 的结点中，选、不选 $i$ 号点时的最大独立集大小。
考虑 $u$ 与 $x=p_u$ 的关系。
这种情况最为简单。若 $x$ 选了，则 $u$ 不能选。若 $x$ 不选，则 $u$ 可选可不选。
$f_x=f_x+g_u$，$g_x=g_x+\max(f_u,g_u)$。
这种情况比较复杂。
若 $x$ 选了，则 $u$ 可选可不选。
若 $x$ 没选，$u$ 也没选，则没有任何影响。
若 $x$ 没选，$u$ 选了，就需要进行考虑，因为此时比 $u$ 编号小的，且是 $x$ 的朋友的点都不能选了。
由于我们是自底向上考虑转移的，因此可以按照编号从大到小转移。那么转移到 $u$ 的时候，比 $u$ 编号大的都已经转移完毕了。所以我们可以认为编号大于 $u$ 的点都已经被删掉，不需要考虑。
这个时候，若 $u$ 选了而 $x$ 没选，则与 $x$ 直接连边的点都是不能选的。那么我们就可以认为是选了 $x$ 而导致了与 $x$ 有连边的点不能选，将 $g_x+f_u$ 转移状态到 $f_x$ 上即可。由于 $u$ 之后的状态都已经转移过了，因此不会产生影响。
那么转移为：$f_x=\max(f_x+\max(f_u,g_u),g_x+f_u)$，$g_x=g_x+g_u$。
和第二种情况大致相同，只是在 $x$ 选的时候不能选 $u$ 了。
$f_x=\max(f_x+g_u,g_x+f_u)$，$g_x=g_x+g_u$。
初值 $g_i=0,f_i=\mathrm{confidence}[i]$。
最后答案取 $\max(f_0,g_0)$ 即可。
时空复杂度 $O(n)$。
Code：
#include"friend.h"
#include<algorithm>
int g[100005];
inline void chkmax(int&a,int b){a=std::max(a,b);}
int findSample(int n,int*f,int*p,int*tp){
for(int i=n-1;i;--i)
switch(tp[i]){
case 0:f[p[i]]+=g[i],g[p[i]]+=std::max(f[i],g[i]);break;
case 1:chkmax(f[p[i]]+=std::max(f[i],g[i]),g[p[i]]+f[i]),g[p[i]]+=g[i];break;
case 2:chkmax(f[p[i]]+=g[i],g[p[i]]+f[i]),g[p[i]]+=g[i];
}
return std::max(*f,*g);
}