题目
传送门 to luogu
思路
看到
n
≤
18
n\le 18
n≤18，直接状态压缩。
有一个优化：反正编号最小的“幸存者”迟早要死，你完全可以现在就要求把它干掉。——前提是 每次操作的代价与顺序无关！
还有玄学的优化，就是类似快速枚举子集的方法。看代码吧。主要是这玩意儿太高性能了……
p.s.
\text{p.s.}
p.s.二次函数基础不过关怎么办？拉格朗日硬来吧……
p.s.
\text{p.s.}
p.s.卡精度怎么办？乘个
100
100
100吧……
代码
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std
;
const int MaxN
= 18;
int n
, m
, x
[MaxN
], y
[MaxN
];
long long calculate(int i
,int j
,int x0
){
long long r
= 1ll*x0
*(x0
-x
[j
])*x
[j
]*y
[i
]-1ll*(x0
-x
[i
])*x0
*x
[i
]*y
[j
];
if(r
%(1ll*(x
[i
]-x
[j
])*x
[i
]*x
[j
])) return -1;
return r
/(1ll*(x
[i
]-x
[j
])*x
[i
]*x
[j
]);
}
int dp
[1<<MaxN
], highbit
[1<<MaxN
];
int main(){
for(int i
=0; i
<MaxN
; ++i
)
highbit
[1<<i
] = i
;
for(int i
=0; i
<(1<<MaxN
); ++i
)
if((i
&-i
) != i
)
highbit
[i
] = highbit
[i
-(i
&-i
)];
int T
; scanf("%d",&T
);
while(T
--){
scanf("%d %d",&n
,&m
);
for(int i
=0,a
,b
; i
<n
; ++i
){
scanf("%d.%d",&a
,&b
);
x
[i
] = a
*100+b
;
scanf("%d.%d",&a
,&b
);
y
[i
] = a
*100+b
;
}
for(int i
=1; i
<n
; ++i
)
for(int j
=0; j
<n
-i
; ++j
)
if(x
[j
] > x
[j
+1]){
swap(x
[j
],x
[j
+1]);
swap(y
[j
],y
[j
+1]);
}
for(int S
=1; S
<(1<<n
); ++S
)
dp
[S
] = dp
[S
-(S
&-S
)]+1;
for(int S
=0,id
; S
<(1<<n
)-1; ++S
){
int vanS
= (~S
)&((1<<n
)-1);
id
= highbit
[vanS
&(-vanS
)];
for(int i
=highbit
[vanS
]; i
!=id
; i
=highbit
[((1<<i
)-1)&vanS
])
if(x
[i
] != x
[id
] and x
[id
]*y
[i
]-x
[i
]*y
[id
] < 0){
int newS
= S
;
for(int j
=i
; true; j
=highbit
[((1<<j
)-1)&vanS
]){
if(calculate(id
,i
,x
[j
]) == y
[j
])
newS
|= (1<<j
);
if(not j
) break;
}
dp
[newS
] = min(dp
[newS
],dp
[S
]+1);
}
}
printf("%d\n",dp
[(1<<n
)-1]);
}
return 0;
}
后记
什么叫做高性能？
时限是
2
s
⋯
⋯
2s\cdots\cdots
2s⋯⋯
再看看另一位大佬的搜索做法：（
PPL orz or2 orz
\text{PPL orz or2 orz}
PPL orz or2 orz）
顺便安利一下这位大佬的博客。
