【题解】NOIP2016愤怒的小鸟

一眼n<=18状压dp……方程什么的都很显然，枚举两只小鸟，再将这条抛物线上的小鸟抓出来就好啦。只是这样O(n^3)的dp必然是要TLE的，我一开始这样交上去显然跑得巨慢无比，后来转念一想：面对一个崭新的情况的时候，只有搭配的优劣之分，没有先后的区别，所以最外面的一层可以直接去掉，变成O(n^2)的dp。这样就跑的很快啦~

PS:print()函数只是调试输出，作用是输出now 的二进制形式+dp[now]；

#include <bits/stdc++.h>

using namespace std;

#define db double

#define eps 0.00000001

#define maxn 30

#define maxm (1 << 18) + 20

#define INF 999999

int T, n, m, dp[maxm], len;

db a, b, x[maxn], y[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void Get_ab(db x1, db y1, db x2, db y2)

{

    a = (y1 * x2 - y2 * x1) / (x1 * x1 * x2 - x2 * x2 * x1);

    b = (x2 * x2 * y1 - x1 * x1 * y2) / (x1 * x2 * x2 - x1 * x1 * x2);

}

bool On_Line(db x1, db y1)

{

    db r = x1 * x1 * a + x1 * b;

    if((r - y1 < eps) && (r - y1 > -eps)) return true;

    else return false;

}

void print(int now)

{

    int a[], tot = ;

    int k = now;

    while(k)

    {

        a[++ tot] = k & ;

        k >>= ;

    }

    cout << now << " ";

    for(int i = ; i <= tot; i ++) cout << a[i];

    for(int i = n; i > tot; i --) cout <<'';

    cout << " " << dp[now];

    cout << endl;

}

void DP(int now)

{

    if(dp[now] != INF) return;

    for(int i = ; i < n; i ++)

    {

        if((( << i) & now)) continue;

        for(int j = i + ; j < n; j ++)

        {

            if(x[i] == x[j]) continue;

            Get_ab(x[i], y[i], x[j], y[j]);

            if(a >= ) continue;

            int aft = ;

            for(int k = ; k < n; k ++)

                if(On_Line(x[k], y[k])) aft = (aft | ( << k));

            int tem = aft | now;

            DP(tem);

            dp[now] = min(dp[now], dp[tem] + );

        }

        int aft = ( << i);

        int tem = aft | now;

        DP(tem);

        dp[now] = min(dp[now], dp[tem] + );

        break;

    }

}

void init()

{

    len = ( << n) - ;

    for(int i = ; i < len; i ++) dp[i] = INF;

}

int main()

{

    T = read();

    while(T --)

    {

        n = read(), m = read();

        init();

        for(int i = ; i < n; i ++)

            scanf("%lf%lf", &x[i], &y[i]);

        dp[len] = ;

        DP();

        printf("%d\n", dp[]);

    }

    return ;

}

巴特西

【题解】NOIP2016愤怒的小鸟

最新文章

热门文章