Description

Solution

一题很显然的状压DP，
显然的转移是 n3 的，
优化：
1. 很显然两个点决定一条抛物线后，可以预处理还能打到那些点。
2. 贪心的想，既然一个点迟早要打，为何不现在就打了它，

复杂度： O(2n∗n)

Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef double db;
const int N=20;
int n,m,ans,m_;
db a[N][2];
int f[524300];
int g[N][N];
int er[20];
int d[524300];
bool OK(int q,int w,int e)
{
db A,t,B;
db x1=a[q][0],x2=a[w][0];
db y1=a[q][1],y2=a[w][1];
t=x1/x2;
A=(y1-t*y2)/(x1*x1-t*x2*x2);
if(A>1e-6)return 0;
B=(y1-A*x1*x1)/x1;
x1=a[e][0];
y1=a[e][1];
if(y1<=A*x1*x1+B*x1+1e-6&&y1>=A*x1*x1+B*x1-1e-6)return 1;
return 0;
}
int min(int q,int w){return q<w?q:w;}
int main()
{
freopen("angrybirds.in","r",stdin);
freopen("angrybirds.out","w",stdout);
int q,w,_;
er[1]=1;fo(i,2,19)er[i]=er[i-1]<<1;
scanf("%d",&_);
while(_--)
{
scanf("%d%d",&n,&m_);
fo(i,1,n)scanf("%lf%lf",&a[i][0],&a[i][1]);
ans=1e9;
if(m_==1)ans=n/3+2;
fo(i,1,n-1)
fo(j,i+1,n)
{
g[i][j]=er[i];
fo(k,j,n)if(OK(i,j,k))g[i][j]+=er[k];
}
memset(f,127,sizeof(f));
f[0]=0;
int s=1,t=1;
d[1]=0;
while(s<=t)
{
q=d[s++];
if(q==er[n+1]-1||f[q]>=ans)continue;
for(w=1;q&er[w];w++);
if(f[q+er[w]]>f[q]+1)f[q+er[w]]=f[q]+1,d[++t]=q+er[w];
fo(i,w+1,n)
{
int t1=g[w][i]&(er[n+1]-1-q);
if(f[q+t1]>f[q]+1)f[q+t1]=f[q]+1,d[++t]=q+t1;
}
}
printf("%dn",f[er[n+1]-1]);
}
return 0;
}

最后

以上就是傻傻汉堡为你收集整理的【NOIP 2016 提高组】愤怒的小鸟DescriptionSolutionCode的全部内容，希望文章能够帮你解决【NOIP 2016 提高组】愤怒的小鸟DescriptionSolutionCode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。