题目：https://www.luogu.org/problemnew/show/P2831
状压dp。跑得很慢。（n^2*2^n）
注意只打一只猪的情况。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int Lm=;const double eps=1e-;
int T,n,dp[(<<Lm)+],lm,tot,tp,list[Lm*Lm+];
struct Node{
double x,y;
}r[Lm+];
//struct Sit{
// int s,cnt;
//}b[(1<<Lm)+5];
//bool cmp(Sit u,Sit v){return u.cnt<v.cnt;}
//int calc(int s)
//{
// int ret=0;while(s)ret++,s-=(s&-s);return ret;
//}
int solve(int i,int j)
{
double y1=r[i].x,x1=y1*y1,z1=r[i].y;
double y2=r[j].x,x2=y2*y2,z2=r[j].y;
double k=x2/x1;y1*=k;z1*=k;y1-=y2;z1-=z2;
double b=z1/y1,a=(z2-b*y2)/x2;
if(a>=)return -;
int ret=;
for(int p=;p<=n;p++)
if(fabs(r[p].x*r[p].x*a+r[p].x*b-r[p].y)<=eps)ret|=(<<(p-));
return ret;
}
void init()
{
// for(int i=0;i<lm;i++)b[i+1].s=i,b[i+1].cnt=calc(i);
// sort(b+1,b+lm,cmp);
tot=;
for(int i=;i<n;i++)list[++tot]=(<<i);///////////
for(int i=;i<=n;i++) for(int j=i+;j<=n;j++)
{
list[++tot]=solve(i,j);
if(list[tot]==-)tot--;
}
memset(dp,,sizeof dp);dp[]=;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&tp);lm=(<<n);
for(int i=;i<=n;i++)scanf("%lf%lf",&r[i].x,&r[i].y);
init();
for(int i=;i<=tot;i++)
for(int s=;s<lm;s++)
dp[s|list[i]]=min(dp[s|list[i]],dp[s]+);
// for(int i=1;i<=lm;i++)
// {
// int s=b[i].s;
// for(int j=1;j<=tot;j++)
// dp[s|list[j]]=min(dp[s|list[j]],dp[s]+1);
// }
printf("%d\n",dp[lm-]);
}
return ;
}
到处看TJ。发现好像是因为弄了很多冗余状态。
让我们分析为什么当前S一定要打掉第一只未打的猪。（n*2^n）
我们可以把 “前缀连续的1多了一个” 看做更进了一步。反正最后要 “前缀连续的1有n个” ，所以这样看也还行。
那么不打第一只未打的猪的转移就是同层转移了。这种转移不能使我们离最终状态更近。
但是它可以让后面的0更少之类的，可能对后面有好的影响。
分析一下这里：如果现在打了后面、后面再补回来现在这个“第一只未打的猪”可以更优的话，因为打猪的顺序无关，所以可以对应成现在打了“第一只未打的猪”、后面打了本回可能会打的那些猪。
所以可以n*2^n。（一下子就快了10倍呢）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int Lm=;const double eps=1e-;
int T,n,dp[(<<Lm)+],lm,tp,list[Lm+][Lm+];
double x[Lm+],y[Lm+];
int solve(int i,int j)
{
double a=(y[i]*x[j]/x[i]-y[j])/(x[i]*x[j]-x[j]*x[j]);
double b=y[i]/x[i]-a*x[i];
if(a>=-eps)return ;
int ret=;
for(int u=;u<=n;u++)
if(fabs(x[u]*x[u]*a+x[u]*b-y[u])<=eps)ret|=(<<(u-));
return ret;
}
void init()
{
for(int i=;i<=n;i++)
{
list[i][i]=(<<(i-));
for(int j=i+;j<=n;j++)
list[i][j]=solve(i,j);
}
memset(dp,,sizeof dp);dp[]=;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&tp);lm=(<<n);
for(int i=;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
init();
for(int s=;s<lm;s++)
{
int i;
for(i=;i<=n&&(s&(<<(i-)));i++);
for(int j=i;j<=n;j++)dp[s|list[i][j]]=min(dp[s|list[i][j]],dp[s]+);
}
printf("%d\n",dp[lm-]);
}
return ;
}
但还不够优秀。翻翻洛谷提交记录，看到“文文殿下”惊人的时间，就去学习。
其实就是用bfs来写。加上第2版的那个优化。
这样可以得到答案及时退出而不用担心答案不最优（因为是bfs）。
这大约是利用了 每次转移都只会+1 的性质。能用bfs的话还是它最快呢。（0ms）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int Lm=,INF=;const double eps=1e-;
int T,n,lm,tp,list[Lm+][Lm+];
int h,t,q[(<<Lm)+],dfn[(<<Lm)+];
double x[Lm+],y[Lm+];
bool vis[(<<Lm)+];
int solve(int i,int j)
{
double a=(y[i]*x[j]/x[i]-y[j])/(x[i]*x[j]-x[j]*x[j]);
double b=(y[i]/x[i]-a*x[i]);
if(a>=-eps)return ;
int ret=;
for(int u=;u<=n;u++)
if(fabs(x[u]*x[u]*a+x[u]*b-y[u])<=eps)ret|=(<<(u-));
return ret;
}
void init()
{
for(int i=;i<=n;i++)
{
list[i][i]=(<<(i-));
for(int j=i+;j<=n;j++)
list[i][j]=solve(i,j);
}
memset(vis,,sizeof vis);
}
void bfs()
{
h=;t=;q[++t]=;dfn[t]=;//t=0,多组数据！
while(h<=t)
{
int s=q[h],d=dfn[h++],i;
for(i=;i<=n&&(s&(<<(i-)));i++);
for(int j=i;j<=n;j++)
{
int x=(s|list[i][j]);if(vis[x])continue;//
vis[x]=;q[++t]=x;dfn[t]=d+;
if(x==lm-){printf("%d\n",dfn[t]);return;}
}
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&tp);lm=(<<n);
for(int i=;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
init();
bfs();
}
return ;
}