愤怒的小鸟 noip-d2t3 luogu-2831
题目大意：给你n个点，问最少需要多少条经过原点的抛物线将其覆盖。
注释：1<=点数<=18，1<=数据组数<=30。且规定抛物线是开口向下的。
想法：其实一开始的想法是很偏的，就是设dp[i][j][k]表示在状态k下建立$i_{th}$和$j_{th}$的抛物线的最少条数，然后向后转移。这显然是错误的，错误原因在于… 我日，没个转移。然后看了一下lijinnn的题解…啊？切了。
是这样的，我们通过记录每条抛物线所能覆盖的点，将其记录在数组str中，不分先后顺序。然后，我们考虑状态
dp[s]表示达到s状态的最少条数。
转移：
dp[s]=min(dp[ s ] , dp[ s ^ ( s & str[ i ] ) ] + 1);
最后，附上丑陋的代码… …
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef double db;
db ax[30],ay[30];
int n,m;
db ka,kb;
int str[1000100],cnt,dp[300100];
bool visit[1003000];
void dispose(int x,int y)
{
db tmp1=ax[x]*ax[y]*(ax[x]-ax[y]);//------------------------
db tmp2=ay[x]*ax[y]-ay[y]*ax[x];// |
if(tmp1<0)// |
{// |
tmp1=-tmp1,tmp2=-tmp2;// |
}// |
if(fabs(tmp1)<1e-6)// |
{// |
return;//我们在计算过这两个点和原点的抛物线解析式 |
}// |
tmp1=tmp2/tmp1;// |
if(tmp1>0)// |
{// |
return;// |
}// |
ka=tmp1;// |
kb=(ay[x]-ka*ax[x]*ax[x])/ax[x];//--------------------------
int s=0;
for(int i=1;i<=n;i++)//枚举所有的点，计算该点是否在当前枚举的抛物线之内
{
db tmp=ax[i]*ax[i]*ka+kb*ax[i];
if(fabs(tmp-ay[i])<1e-6)
{
s+=(1<<(i-1));
}
}
if(!visit[s])
{
visit[s]=1;
str[++cnt]=s;//统计出一条抛物线能够杀死的pig的状态
}
return;
}
void original()
{
memset(visit,0,sizeof visit);
memset(dp,0x3f,sizeof dp);
cnt=0;
}
int main()
{
int cases;
scanf("%d",&cases);
while(cases--)
{
original();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&ax[i],&ay[i]);
}
for(int i=1;i<=n;i++)
{
str[++cnt]=(1<<(i-1));
for(int j=1;j<=i-1;j++)
{
dispose(i,j);
}
}
dp[0]=0;
for(int s=0;s<(1<<n);s++)
{
for(int i=1;i<=cnt;i++)
{
if(s&str[i])
{
dp[s]=min(dp[s],dp[s^(s&str[i])]+1);//转移方程
}
}
}
printf("%d\n",dp[(1<<n)-1]);
}
return 0;
}
小结：状态的选取决定着动态规划的走势—-某乎上的dalao说的
