NOIP 2016系列解题报告 – [题组/NOIP]

Day2 T3 愤怒的小鸟

你可以点击这个链接下载全部的AC代码

题目传送门(LOJ)

题解 :

​ 两个小猪确定一条抛物线,把所有抛物线列出来,并枚举其他小猪来确定这条抛物线能打掉哪些小猪

把状态压缩,然后直接从 0 到 (1<<n)-1做状压DP即可。

​ 确定抛物线的时候,我们先枚举两个小猪,设坐标 (x_1, y_1), (x_2, y_2) 由题意得

a = \frac{y_2-\frac{y_1x_2}{x_1}}{x_2^2-x_1x_2} b = \frac{y_2-\frac{y_1x_2^2}{x_1^2}}{x_2-\frac{x_2^2}{x_1}} 嗯,我们就这样确定了一个方程,反正有电脑帮着算,我才懒得化简。

对了,为了不被hack,我们要确定一些东西,比如 a<0 啊,anan 啊什么的,都要判掉,然后必然一条线至少可以打掉一个,所以我们还要加 n 条只能打掉一只小猪的线。最后状压DP 就好啦!

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注