[NOIP2016]愤怒的小鸟（状压DP）

89 阅读 0 评论 59 点赞

我是靠谱客的博主虚拟香水，这篇文章主要介绍[NOIP2016]愤怒的小鸟（状压DP），现在分享给大家，希望可以做个参考。

[NOIP2016]愤怒的小鸟（状压DP）

题目描述

输入输出格式

输入格式：

第一行包含一个正整数 T，表示游戏的关卡总数。

下面依次输入这 T个关卡的信息。每个关卡第一行包含两个非负整数 n,m，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 n行中，第 ii 行包含两个正实数 $xi,yi$ ，表示第 i只小猪坐标为 $xi,yi$ 。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 m=0，表示Kiana输入了一个没有任何作用的指令。

如果 m=1，则这个关卡将会满足：至多用 $left lceil n/3+1 right rceil$ 只小鸟即可消灭所有小猪。

如果 m=2，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 $left lfloor n/3 right rfloor$ 只小猪。

保证 $1leq nleq 18,0leq mleq 2,0<xi,yi<10$

输出格式：

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。

输入输出样例

输入样例#1：

复制代码

输出样例#1：

复制代码

输入样例#2：

复制代码

输出样例#2:

复制代码

输入样例#3： 复制

复制代码

输出样例#3：

复制代码

1
6

说明

【样例解释1】

这组数据中一共有两个关卡。

第一个关卡与【问题描述】中的情形相同，22只小猪分别位于(1.00,3.00)(1.00,3.00)和 (3.00,3.00)(3.00,3.00)，只需发射一只飞行轨迹为y = -x^2 + 4xy=−x2+4x的小鸟即可消灭它们。

第二个关卡中有55只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y = -x^2 + 6xy=−x2+6x上，故Kiana只需要发射一只小鸟即可消灭所有小猪。

【数据范围】

Solution

（我们知道三点确定一个抛物线，此处的n<=18）

枚举两头猪，设坐标为 $(x1,y1),(x2,y2)$ ，以 $(0,0),(x1,y1),(x2,y2)$ 作抛物线，求出抛物线上有哪些猪，记为： $g[i,j]$

于是 $f[i|g[j][k]]=min(f[i|g[j][k]],f[i]+1)$

这显然是一个 $o(2^{n}n^{2})$ 的做法，似乎不太优秀。

事实上，这个DP有可优化之处：每一次枚举的抛物线必须包含未消灭的第一头猪！

Because枚举的抛物线的顺序与最优解无关，并且未消灭的猪在之后的抛物线中必须被覆盖到至少一次，那么与其先覆盖其他的猪，不如直接先覆盖第一头未消灭的猪，这对答案是没有影响的。因此，每一次转移只需要枚举能覆盖第一头未消灭的猪的抛物线即可。

改变了转移之后，时间复杂度变为 $o(2^{n}n)$ ，轻松AC。

复制代码

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
using namespace std;
template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }
typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;
const lod eps=1e-6;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=1e9+7;
const int MAXN=20;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
int w=0; bool q=1; char c=getchar();
while ((c<'0'||c>'9')&&c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?w:-w;
}
int g[MAXN][MAXN],s[MAXN],f[(1<<MAXN)+5];
double x[MAXN],y[MAXN];
inline bool check(double x,double y){ return abs(x-y)<eps; }
int main(){
s[0]=1;
for (int i=1;i<=19;i++) s[i]=s[i-1]<<1;
int Case=read();
while (Case--){
int n=read(),m=read();
for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
memset(g,0,sizeof(g));
memset(f,INF,sizeof(f)); f[0]=0;
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++) {
if (check(x[i],x[j])) continue; double a=(y[j]/x[j]-y[i]/x[i])/(x[j]-x[i]);
if (a>=0)
continue; double b=y[i]/x[i]-a*x[i];
for (int k=1;k<=n;k++) g[i][j]+=s[k-1]*(check(a*x[k]+b,y[k]/x[k]));
}
for (int i=0;i<=s[n]-1;i++)
for (int j=1;j<=n;j++)
if (!(i&s[j-1])){
for (int k=j+1;k<=n;k++) upmin(f[i|g[j][k]],f[i]+1);
upmin(f[i|s[j-1]],f[i]+1);
}
printf("%dn",f[s[n]-1]);
}
return 0;
}

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
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
//#include <unordered_set>
//#include <unordered_map>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se second
using namespace std;
template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; }
template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }
typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;
const lod eps=1e-6;
const lod pi=acos(-1);
const int oo=1<<30;
const ll loo=1ll<<62;
const int mods=1e9+7;
const int MAXN=20;
const int INF=0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{
int w=0; bool q=1; char c=getchar();
while ((c<'0'||c>'9')&&c!='-') c=getchar();
if (c=='-') q=0,c=getchar();
while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?w:-w;
}
int g[MAXN][MAXN],s[MAXN],f[(1<<MAXN)+5];
double x[MAXN],y[MAXN];
inline bool check(double x,double y){ return abs(x-y)<eps; }
int main(){
s[0]=1;
for (int i=1;i<=19;i++) s[i]=s[i-1]<<1;
int Case=read();
while (Case--){
int n=read(),m=read();
for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
memset(g,0,sizeof(g));
memset(f,INF,sizeof(f)); f[0]=0;
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++) {
if (check(x[i],x[j])) continue; double a=(y[j]/x[j]-y[i]/x[i])/(x[j]-x[i]);
if (a>=0)
continue; double b=y[i]/x[i]-a*x[i];
for (int k=1;k<=n;k++) g[i][j]+=s[k-1]*(check(a*x[k]+b,y[k]/x[k]));
}
for (int i=0;i<=s[n]-1;i++)
for (int j=1;j<=n;j++)
if (!(i&s[j-1])){
for (int k=j+1;k<=n;k++) upmin(f[i|g[j][k]],f[i]+1);
upmin(f[i|s[j-1]],f[i]+1);
}
printf("%dn",f[s[n]-1]);
}
return 0;
}