题解 P2831 【愤怒的小鸟】
suncongbo
2017-09-14 21:36:24
，第一篇题解，有不妥之处请见谅
思路：
# 解法：状压DP.
g[x]表示二进制编码为x的状态所用的最小步数。
sol[i]表示第i组解。解共有s组。
二进制编码：
状压DP基本概念，二进制数每一位的1表示可以达到这个点，0表示不能达到这个点。
比如，g[10101001]（二进制）表示达到第1，4，6，8个点（十进制）所用的最少抛物线数。
解： 能通过仅1条抛物线所达到的所有的点组成的二进制编码，叫做一个解。
本题主要分为以下几步：
预处理。此处可用递归。首先枚举两个点，通过两个点共抛物线构造二元一次方程，用公式将其解出。
公式：a1x+b1y=c1,a2x+b2y=c2,解得x = (b2\*c1-b1\*c2)/(a1\*b2-a2\*b1), y = (a1\*c2-a2\*c1)/(a1\*b2-a2\*b1).
DP。此处可以理解为01背包。背包容量为(1<<n)-1，共s个物品，费用分别为sol[1],sol[2],...,sol[s]，价值均为1，且要求把背包装满，求最小价值。
但是有一个极大的漏洞：比如我们要配出（以下均为二进制）10011000这个数，一种正确的配法是10000000+00011000，但是另一种拼法是10000000+00010111+00000001，发生了进位，虽然和依然是10011000，但是第1个点显然被打了2次。
改进方法：另加一重循环，判断是否有重复。时间复杂度O(n)
本步总时间复杂度：O(smn)，其中m=1<<n，可以证明s<=n^2/2，故复杂度O(2^n\*n^3)，期望得分75~85分。
优化
不难发现，比如一条抛物线恰好打中了1，4，6，8（均为十进制）这四个点，且不能打中其他的点。则这条抛物线使s的值增加了15（即(1),(4),(6),(8),(1,4),(1,6),(1,8),(4,6),(4,8),(6,8),(1,4,6),(1,4,8),(1,6,8),(4,6,8),(1,4,6,8).事实上，由于我们是用最少的抛物线打最多的点，因此最后一种(1,4,6,8)的方案比前14种的任意一种都更优。因此，只需在无法继续递归（即没有其他点可以打）时将方案添加到sol[s]中，很大程度上降低了s的大小。（但并不能改变最坏复杂度，因为有可能特造一数据使得无任意三点共抛物线）
最重要的优化：我们在背包中进行位运算判断是否重复，因此添加了重复的情况还要舍去，多一维复杂度。不妨逆向思考：g[j]=min(g[j],g[j-sol[i]+1),原来可以用要更新的点j的编号来表示用来更新此点的点j-sol[i]，现在可以用用来更新此点的点的编号来表示此点。即用g[j]来更新其他点，而不是用其他点来更新g[j].这样，我们就可以写出被更新的点的编号：g[i|sol[j]].
注意：二进制原来1+1=10，现在1|1=1，不会发生进位，因此无需特判，减小一维复杂度。
## 总复杂度：O(s\*2^n)，s<=n^2，即O(2^n\*n^2)，期望得分100分。
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = 18;
const int MAXM = 262144;
struct Point
{
double x,y;
};
Point nd[MAXN+2];
int sol[MAXN*MAXN+MAXN];
int g[MAXM+2];
int n,m,c,s;
void solve(double a1,double b1,double c1,double a2,double b2,double c2,double *ansx,double *ansy)
{
if(a1*b2 != a2*b1)
{
*ansx = (b2*c1-b1*c2)/(a1*b2-a2*b1);
*ansy = (a1*c2-a2*c1)/(a1*b2-a2*b1);
}
}
void DFS(int pos,int cod,double a,double b)
{
int i,j;
double arga,argb;
if(pos == n) return;
if(cod == 0)
{
for(i=0; i<n; i++)
{
for(j=i+1; j<n; j++)
{
if(nd[i].x != nd[j].x)
{
solve(nd[i].x*nd[i].x,nd[i].x,nd[i].y,nd[j].x*nd[j].x,nd[j].x,nd[j].y,&arga,&argb);
if(arga < -1e-6)
{
DFS(j,(1<<i)+(1<<j),arga,argb);
}
}
}
}
}
else
{
for(i=pos+1; i<n; i++)
{
if(fabs(nd[i].x*nd[i].x*a+nd[i].x*b-nd[i].y) < 1e-12)
{
DFS(i,cod+(1<<i),a,b);
return;
}
}
sol[s] = cod;
g[cod] = 1;
s++;
}
}
bool match(int spos,int gpos)
{
int i;
for(i=n-1; i>=0; i--)
{
if((sol[spos]&(1<<i)) && (gpos&(1<<i))) return false;
}
return true;
}
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&c);
m = 1<<n;
for(i=0; i<n; i++)
{
scanf("%lf%lf",&nd[i].x,&nd[i].y);
}
if(n == 1)
{
printf("1\n");
continue;
}
memset(g,42,sizeof(g));
memset(sol,0,sizeof(sol));
s = 0;
for(i=0; i<n; i++)
{
sol[s++] = 1<<i;
g[1<<i] = 1;
}
DFS(0,0,0.0,0.0);
g[0] = 0;
for(j=0; j<s; j++)
{
for(i=0; i<m; i++)
{
if(g[i|sol[j]] > g[i]+1) g[i|sol[j]] = g[i]+1;
}
}
printf("%d\n",g[m-1]);
}
return 0;
}
```