#P1416. 攻击火星
攻击火星
题目描述
一群外星人将要攻击火星。
火星的地图是一个 个点的无向图。这伙外星人将按照如下方法入侵,先攻击度为 的点(相当于从图中删除掉它),然后是度为 的点,依此类推直到度为 的点。
所有的点度统计是动态统计的。(一个点删掉后,与之相连的点的点度都会 )。外星人攻击度为某个数的点时是同时攻击的。
你需要设计这个图的边的方案来使得未被攻击的点最多。注意:你设计的图不允许自环及重边。
输入格式
输入文件包含一行一个整数 。
输出格式
一行一个整数,表示最多的最后未被攻击的点。
3
1
提示
【样例解释】
一种可能的方案是 ,这样首先删掉度为 的点 和点 ,此时点 度数为 ,不会被删去。
【数据范围】
- 对于 的数据 ;
- 对于 的数据 。
【题目来源】
tinylic改编