NOIP2016 Day2 T3(状压DP/DFS)

发表于 | 分类于 | | + s

$n$小，搜索或者状压。
设$g(i, j)$为$i$和$j$组成一条抛物线的可被射的鸟的状态，$dp(S)$为在$S$状态时的最优解，然后转移就是
$$dp(S) = min(dp(S-g(i,j))+1)$$
初始化$g(i, j)$需要用待定系数法求出抛物线，即解二元一次方程，这个推一推就能推出通解了，复杂度$O(n^3)$
然后DP求解的时候是$O(2^nn^2)​$，有一点大，所以会TLE了几个点，有空补补$O(2^nn)​$做法

搜索做法：
设$g(i, j)$为$i$和$j$组成一条抛物线的可被射的鸟的状态，然后DFS，加可行性剪枝
DFS里每次看正在搜索的点是否已经被前面打了，用二进制优化，不然就和后面的相连或者一炮只打这一只小鸟，然后更新答案即可，这样做是满分的

2017.09.03: 搜索剪枝满分

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 18 + 1;
const double eps = 1e-12;
void jfc(double &x, double &y, double a, double b, double c, double d, double e, double f) {
    //ax+by=e
    //cx+dy=f
    if ((a * d - c * b) == 0 || a == 0) {x = 1, y = 1; return;}
    y = (a * f - c * e) / (a * d - c * b);
    x = (e - b * y) / a;
}
int n, m, p[MAXN][MAXN], f[MAXN][1 << MAXN], ans;
db xi[MAXN], yi[MAXN];
void dfs(int a, int st, int used) {
    if (a == n + 1) {
        ans = min(ans, used);
        return ;
    }
    if (used >= ans) return ;
    if (used >= f[a][st]) return ;
    f[a][st] = used;
    if (st >> (a - 1) & 1) dfs(a + 1, st, used); else {
        for (int i = a + 1; i <= n; i++) {
            dfs(a + 1, st | p[a][i], used + 1);
        }
        dfs(a + 1, st, used + 1);
    }
}
void clean() {
    ans = 1000000000;
    ms(p, 0), ms(f, 127);
}
void solve() {
    scanf("%d%d", &n, &m);
    clean();
    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf", &xi[i], &yi[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            p[i][j] = (1 << (i - 1));
            db nowx, nowy;
            jfc(nowx, nowy, xi[i] * xi[i], xi[i], xi[j] * xi[j], xi[j], yi[i], yi[j]);
            if (nowx >= 0) continue;
            p[i][j] += (1 << (j - 1));
            for (int k = 1; k <= n; k++) {
                if (k != i && k != j) {
                    db orzx, orzy;
                    jfc(orzx, orzy, xi[i] * xi[i], xi[i], xi[k] * xi[k], xi[k], yi[i], yi[k]);
                    if (fabs(orzx - nowx) <= eps && fabs(orzy - nowy) <= eps) p[i][j] += (1 << (k - 1));
                }
            }
        }
    }
    dfs(1, 0, 0);
    printf("%d\n", ans);
}
int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}

$O(2^nn^2)$做法(状压)：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 18 + 2;
const double eps = 0.000000001;
int n, m, g[MAXN][MAXN], dp[1<<MAXN];
double xi[MAXN], yi[MAXN];
void jfc(double &x, double &y, double a, double b, double c, double d, double e, double f) {
    //ax+by=e
    //cx+dy=f
    if ((a*d-c*b)==0||a==0) {x = 1, y = 1; return;}//除0会炸 
    y = (a*f-c*e)/(a*d-c*b);
    x = (e-b*y)/a;
}
void clean() {
    ms(g, 0), ms(dp, 67);
}
__attribute__((optimize("-O2")))
void solve() {
    scanf("%d%d", &n, &m);
    clean();
    for (int i=1;i<=n;i++) scanf("%lf%lf", &xi[i], &yi[i]);
    for (int i=1;i<=n;i++) {
        for (int j=i;j<=n;j++) if (!g[i][j]) { 
            double x, y; 
            if (i==j) {g[i][j] = (1<<(i-1)); continue;}//特判一下一个点 
            jfc(x, y, xi[i]*xi[i], xi[i], xi[j]*xi[j], xi[j], yi[i], yi[j]);
            if (x>=0) continue;
            g[i][j] = (1<<(i-1)); 
            g[i][j] += (1<<(j-1));
            for (int k=1;k<=n;k++) 
            if (i!=k&&j!=k) {
                double dx, dy; 
                jfc(dx, dy, xi[i]*xi[i], xi[i], xi[k]*xi[k], xi[k], yi[i], yi[k]);
                if (dx>=0) continue;
                if (fabs(dx-x)<=eps&&fabs(dy-y)<=eps) g[i][j] += (1<<(k-1));
            }
            g[j][i] = g[i][j];
        }
    }
    dp[0] = 0;
    for (int S=1;S<(1<<n);S++) {
        if (S==(1<<n)-1) 
        dp[0] = dp[0];
        for (int i=1;i<=n;i++) {
            if (S&(1<<(i-1))) {
                for (int j=1;j<=n;j++) {
                    if ((S&(1<<(j-1)))&&((S&g[i][j])==g[i][j])) {
                        dp[S] = min(dp[S], dp[S^g[i][j]]+1);
                    }
                }
            }
        }
    }
    printf("%d\n", dp[(1<<n)-1]);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}
------ 本文结束 ------