NOIP2016 愤怒的小鸟

题目传送门

题解

状压DP。 将每一只猪打下来/没打下来用一个二进制位表示。 猪的数量不是很多,每一条抛物线至少要打到一只猪,所以可以枚举出所有可行的抛物线,这条抛物线对每一只猪能/不能打下来用一个二进制为表示。

当然只能打到1只猪的抛物线不用枚举,一开始就加进去它的表示就行。 枚举两只猪,如果它们不在同一列,则将它们的坐标x,y分别代入方程y=ax2+bxy=ax^2+bx,解得a,b,如果这组a,b没有没找到过且a为负,则用这组a,b尝试对每一只猪尝试看能不能打到。 设找到的第i条对角线可以打到的状态为aia_i,一共有m条对角线。 设fif_i表示是否被打到的状态为i时还需要的最少抛物线数。 则状态转移方程为fi=minj=1m{f[iora[j]]}+1f_i=min_{j=1}^{m}\{f[i or a[j]]\}+1,边界条件f[2n1]=0f[2^n-1]=0注意当iora[j]=ii or a[j]=i时不要转移。 f[0]f[0]就是最终的答案。 其中or是按为与运算。 为了防止实数精度误差,要用eps来防精度误差,但是实数判断的eps要开小一点,否则过不了extratest

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
Author: CNYALI_LK
LANG: C++
PROG: luogu2831.cpp
*/
#include<bits/stdc++.h>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define go(a,b) for(int a=0;a<b;++a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const long double eps=1e-8;
const long double PI=acos(-1.0);
typedef long long ll;
typedef pair<long double,long double> pii;
#define x first
#define y second
#define mp make_pair
struct inout{
//io优化被省略
};
inout io;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
set<pii> st;

int m[1024];
long double x[1024],y[1024];
pii js(int a,int b){
long double a_=x[a]*x[a],b_=x[a],c_=y[a];
long double a__=x[b]*x[b],b__=x[b],c__=y[b];
a_*=b__/b_;
c_*=b__/b_;
b_=b__;
a_-=a__;
c_-=c__;
c_/=a_;
a_=1;
c__-=a__*c_;
a__=0;
c__/=b__;
return mp(c_,c__);
}
int same(long double a,long double b){
return fabs(a-b)<eps;
}
int chk(pii a,int b){
return same(a.x*x[b]*x[b]+a.y*x[b],y[b]);
}
int f[1<<18];
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
io.init();
int t;
pii s;
io>>t;
while(t){
--t;
// printf("MMP%d\n",t);
int n,yycsb,tt=0;
io>>n>>yycsb;
yycsb=1<<n;
go(i,n){
io>>x[i]>>y[i];
m[tt]=1<<i;
++tt;
}
st.clear();
go(i,n-1){
up(j,i+1,n-1){
if(same(x[i],x[j]))continue;//判断不在同一列
s=js(i,j);//解方程
if(s.x>=-0.000001)continue;//防精度误差
if(st.count(s)){continue;}
st.insert(s);
m[tt]=0;
go(k,n)if(chk(s,k))m[tt]|=1<<k;//计算能打到那些猪。
++tt;
}
}
f[yycsb-1]=0;
for(int i=yycsb-2;i>=0;--i){
f[i]=0x3f3f3f3f;
go(j,tt)if((m[j]|i)^i)chkmin(f[i],f[i|m[j]]);
++f[i];
}
io<<f[0]<<endl;
}
io.out();
return 0;
}
文章目录
  1. 1. 题解
  2. 2. 代码
|

博客使用Disqus作为评论系统