题目描述
Kiana最近沉迷于一款神奇的游戏无法自拔。
简单来说,这款游戏是在一个平面上进行的。
有一架弹弓位于 (0, 0) 处,每次Kiana可以用它向第一象限发射一只红色的小鸟, 小鸟们的飞行轨迹均为形如 y = ax2 + bx 的曲线,其中 a, b 是Kiana指定的参数,且必须满足 a < 0 。
当小鸟落回地面(即 x 轴)时,它就会瞬间消失。
在游戏的某个关卡里,平面的第一象限中有 n 只绿色的小猪,其中第 i 只小猪所在的坐标为 (xi, yi) 。
如果某只小鸟的飞行轨迹经过了 (xi, yi) ,那么第 i 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;
如果一只小鸟的飞行轨迹没有经过 (xi, yi) ,那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。
例如,若两只小猪分别位于 (1, 3) 和 (3, 3) ,Kiana可以选择发射一只飞行轨迹为 y = −x2 + 4x 的小鸟,这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对Kiana来说都很难,所以Kiana还输入了一些神秘的指令,使得自己能更轻松地完成这个这个游戏。
这些指令将在输入格式中详述。
假设这款游戏一共有 T 个关卡,现在Kiana想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。
由于她不会算,所以希望由你告诉她。
注意:本题除NOIP原数据外,还包含加强数据。
样例
输入
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00
输出
1
1
算法1- 状压Dp
$O(T(n^3 + n2^n))$
题意:最少需要几只小鸟才能将所有的小猪🐖消灭。
根据本题的数据范围,可以考虑用状态压缩Dp来处理:
下面依次思考几个问题:
抛物线的问题
由于本题中抛物线严格经过原点,所以c=0,那么只需要两点我们就可以确定一条抛物线$y=ax^2+bx$
所以我们可以用两个小猪确定一个可以消灭它们的抛物线,考虑如何表示这个变量:
path数组
path[i][j]
表示编号为i的小猪和编号为j的小猪所在的抛物线,变量的属性为这个抛物线可消灭的小猪(编号)的二进制状态表示
eg: path[2][3]
= 100111
表示由2号猪和3号猪确定的抛物线可以消灭编号1,2,3,6
的小猪。下面考虑状态的表示和计算:
f数组
状态表示: f[i]
表示当前击败状态i表示的小猪所需要的最少的小鸟。
状态计算: 找到i
状态下没有被消灭的小猪的编号x,枚举可消灭它的抛物线path[x][j]
并更新状态:
f[i | path[x][j]] = min(f[i | path[x][j]] , f[i] + 1);
还有一些细节在注释中体现
时间复杂度$O(T(n^2)(2^n))$
参考文献
算法提高课
C++ 代码
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef pair<double,double> pdd;
const int N = 18, M = 1<<18;
const double eps = 1e-6;
pdd q[N];
int path[N][N]; //path[i][j] 表示第i个点和第j个点构成的抛物线能覆盖的点的状态
int f[M];
int T,n,m;
bool cmp(double a,double b){
if(fabs(a-b)<eps) return true; // a == b
return false;
}
int main()
{
IO;
cin>>T;
while(T--){
cin>>n>>m;
for(int i = 0; i<n; i++) cin>>q[i].first>>q[i].second;
memset(path,0,sizeof path); //清空
for(int i = 0; i<n; i++){
path[i][i] = 1<<i;
for(int j = 0; j<n; j++){
double x1 = q[i].first,x2 = q[j].first;
double y1 = q[i].second,y2 = q[j].second;
//计算抛物线y = a(x^2) + bx
if(cmp(x1,x2)) continue; //抛物线上不存在斜率为无限大的切线
double a = (y1/x1-y2/x2)/(x1-x2);
double b = (y1/x1-a*x1);
if(a>0 || cmp(a,0.0)) continue; //此题抛物线需开口向下
//计算path[i][j]的能覆盖的点的状态
for(int k = 0; k<n; k++){
double x = q[k].first, y = q[k].second;
if(cmp(a*x*x +b*x,y)) path[i][j] += 1<<k; //这一点在这条抛物线上
}
}
}
memset(f,0x3f,sizeof f); //清空
f[0] = 0;
for(int i = 0; i <1<<n; i++){ //遍历所有状态
int x = 0;
for(int j = 0; j<n; j++){
if(i>>j&1) continue; //找到状态i中没覆盖的点的标号
x = j;
break;
}
for(int k = 0; k<n; k++)
f[i | path[x][k]] = min(f[i | path[x][k]], f[i] + 1);
//cout<<i<<" "<<f[i]<<endl;
}
cout<<f[(1<<n)-1]<<endl;
}
return 0;
}
太强了,写得好清楚!!!
看Y总题解没看懂,看您的看懂了,感谢🎁!
666
同问:为什么转移时随便找到当前未被覆盖的某一列 xx,然后枚举所有包含 xx 的行j来选择即可,而不是遍历所有情况???
O(T(n2)(2n))是啥意思,好潮阿
写的好清楚!!!谢谢
太强了,写得很好
path[2][3] = 100111 表示由2号猪和3号猪确定的抛物线可以消灭编号1,2,3,6的小猪。
应该是消灭1,4,5,6 吧
从右往左看哟
path[i][i] = 1<<i;和path[i][j] += 1<<k; 什么意思,没太懂
y总变量名取的不好,把path叫做parabola更合适一点,后面的两个框里表示这个parabola是由这两个框表示的猪构建出来的,加上1 << 某个数的意思就是说能打到某个数表示的猪。因为题目最多只有18头猪给你打,int是32位的,所以其实能表示32头猪。这里其实做的就是先枚举一下所有的由任意两头猪构成的抛物线,然后再看看这些抛物线里的每一条除了能打到构建它的两头猪以外,还能打到别的什么猪没有。
tql,写的太好了!
清晰
非常感谢
写的真好,非常感谢!!
非常清晰,牛逼 Orz
为什么任选一列进行覆盖进行转移就行啊?不应该对每一个没覆盖的点进行尝试吗?
其实这个做法只能保证对f[(1 << n) - 1]是对的,中间状态f[i]不一定所有都是有效的(不一定所有f[i]的值是最少抛物线数量),只有部分中间状态是有效的,注意i从零开始,每次更新的时候i | path[j][k]一定是大于i的,因此从0开始更新有效状态,之后i++的时候一定会走到这个有效状态,然后继续更新下一个有效状态。
然后任选一列就可以是因为,对于任意一个点x,他所有抛物线的可能性都会在上述更新过程中被记录到,并进行有效更新。
从第三个题解的记忆化搜索的角度看会好一点,这里遍历其实做了很多无用功。记忆化搜索快多了。
明白啦!多谢!!
这么一说就清楚多了,%%谢佬!
这么说这里是能够保证最后一个状态时正确的(全1),所以很多状态压缩其实都可以这样来写。
这里如果是多加一层循环来枚举所有没有被击败的猪,则中间所有的
f[i]
都是有效的?我觉得是
写的真好
请问一下 为什么最后输出的结果是f[(1 << n) -1]呢? 作者能不能详细说明一下 谢谢
f[state]
:覆盖state中点的最小抛物线数量所以
f[(1 << n) -1]
表示包含状态11111…… (所有点)的最小抛物线数量thanks
一起努力啦~
%%%%%