uva11008 - Antimatter Ray Clearcutting(二進制+記憶化搜索）
題目大意：給出n棵樹的坐標，每次砍樹能夠將在同一直線上的樹一起砍掉，然後給出要求你至少砍掉的樹的數量，問你要達到這個要求需要砍多少次。
解題思路：因為這題的樹的數量比較小（16）， 並且只有砍和不砍兩種選擇，可以用二進制數將狀態表示出來。大致思路是：每次都將當前狀態下的還沒砍的樹中選擇兩棵，在將和這兩個樹在同一直線上的樹一起砍掉，得到新的狀態。如果已經》=K棵了，就可以返回0了。一般來說，每次選擇兩棵樹一起砍掉比較優，除非只剩下一棵樹了。所以應該要先預處理出每兩棵樹和它們在同一直線上的樹，並且這個狀態可以也用二進制表示。
代碼：
#include
#include
const int maxn = 1<<17;
const int M = 20;
int dp[maxn];
int n, k;
int tree[M][2];
int line[M][M];
bool judge (int i, int j, int k) {
int a = (tree[j][1] - tree[i][1]) * (tree[k][0] - tree[j][0]);
int b = (tree[k][1] - tree[j][1]) * (tree[j][0] - tree[i][0]);
return a == b ? true : false;
}
int Min (const int a, const int b) { return a < b ? a: b; }
void init () {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
line[i][j] = 0;
for (int l = 0; l < n; l++) {
if (judge (i, j, l)) {
line[i][j] |= (1<= k)
return ans = 0;
int flag = 0;
for (int i = 0; i < n; i++) {
if (((1 << i) & s) == 0) {
for (int j = i + 1; j < n; j++) {
if (((1 << j) & s) == 0) {
flag = 1;
ans = Min (ans, DP(s | line[i][j]) + 1);
//printf (%d %d %d
, s, s | line[i][j], ans);
}
}
if (!flag) {
ans = Min (ans, DP(s | (1<
