题解 P2831 【愤怒的小鸟】

· · 个人记录

【题意简述】

平面的第一象限内有n只小猪，第i只坐标为(xi ,yi)。有一架弹弓位 于(0,0)处，每次你可以用它发射一只小鸟，小鸟的飞行轨迹是一条形 如y=ax^2+bx的开口向下的抛物线。求最少发射多少小鸟，使得所有 小猪都被消灭。

n\le18

【题目简析】

此处摘录自https://www.luogu.org/blog/1000suns/solution-p2831

设计dp状态：

$dp[S]$表示已经死了的猪的集合状态为 $S$ 时最少要发射的鸟数。 明显有 > $dp[0]=0
dp[S|line[i][j]]=\min(dp[S]+1) dp[S|(1<<(i-1)]=\min(dp[S]+1)

其中 line[i][j] 表示经过 i,j 两点的抛物线能经过的所有点的集合。

这就是网上大多流传的 O(Tn^22^n)算法。优化？

优化1：

发现当 i\in S或者j\in S时没有必要转移。

证明：

若这条线只经过至多三个点，因为其中一个点已被打到，所以可以通过另外两个点的状态转移。如果 i,j 都被打到，则可以通过转移3（单独一个点）转移。 若这条线经过多于三个点，则可以通过其它任选两个点转移。 但是这只能算是常数优化。

优化2：

若令x 为满足 S\&(1<<(x-1))=0 的最小正整数，则由S 扩展的转移的所有线都要经过 x。

为什么？这个是对的吗？不经过 x 就会慢吗？

你想一想，先打 1,4，再打 2,3，和先打 2,3，再打 1,4 是不是一样的？

如果这一次转移不打 x，那以后还要再回过头来打 x。这就是多余的转移。

因为经过 x 的线数量是 n，所以每次转移涉及到的线就从 n^2

变成了 n。

只要预处理一下 0-2^{18} 的对应的 x 就能做到 O(Tn2^n)了，这才是考场的正解。

【代码简释】

#include <bits/stdc++.h>
using namespace std ;
const double eps = 1e-10 ;
int T , n , m ;
double x[ 20 ] , y[ 20 ] ;
int lines[ 20 ][ 20 ] ;
int lowunbit[ 1 << 20 ] , dp[ 1 << 20 ] ;
inline void equ ( double &a , double &b , double a1 , double b1 , double c1 , double a2 , double b2 ,double c2 ) { // 解二次函数，求出二次函数的函数关系式（将2个点的坐标带入，即可求得a和b
    b = ( a1 * c2 - a2 * c1 ) / ( a1 * b2 - a2 * b1 ) ;
    a = ( c1 - b1 * b ) / a1 ;
}
signed main () {
    ios :: sync_with_stdio ( false ) ;
    cin >> T ;
    for ( int i = 0 ; i < ( 1 << 18 ) ; i ++ ) {
        int j = 1 ;
        for ( ; j <= 18 && i & ( 1 << ( j - 1 ) ) ; j ++ ) ;
        lowunbit[ i ] = j ;
    } // 预处理出x
    while ( T -- ) {
        memset ( lines , 0 , sizeof ( lines ) ) ;
        memset ( dp , 0x3f , sizeof ( dp ) ) ;
        dp[ 0 ] = 0 ;
        cin >> n >> m ;
        for ( int i = 1 ; i <= n ; i ++ ) {
            cin >> x[ i ] >> y[ i ] ;
        }
        for ( int i = 1 ; i <= n ; i ++ ) {
            for ( int j = 1 ; j <= n ; j ++ ) {
                if ( fabs ( x[ i ] - x[ j ] ) < eps ) continue ;
                double a , b ;
                equ ( a , b , x[ i ] * x[ i ] , x[ i ] , y[ i ] , x[ j ] * x[ j ] , x[ j ] , y[ j ] ) ;
                if ( a > -eps ) continue ;
                for ( int k = 1 ; k <= n ; k ++ ) {
                    if ( fabs ( a * x[ k ] * x[ k ] + b * x[ k ] - y[ k ] ) < eps ) lines[ i ][ j ] |= ( 1 << ( k - 1 ) ) ; // 预处理出经过i，j的抛物线经过点的集合状态
                }
            }
        }
        /*for ( int i = 1 ; i <= n ; i ++ ) {
            for ( int j = 1 ; j <= n ; j ++ ) {
                cout << lines[ i ][ j ] << " " ;
            }
            cout << endl ;
        }*/
        for ( int s = 0 ; s < ( 1 << n ) ; s ++ ) { // 状压DP
            int j = lowunbit[ s ] ;
            //cout << ( 1 << ( j - 1 ) ) << endl ;
            dp[ s | ( 1 << ( j - 1 ) ) ] = min ( dp[ s | ( 1 << ( j - 1 ) ) ] , dp[ s ] + 1 ) ;
            //cout << dp[ s | ( 1 << ( j - 1 ) ) ] << endl ;
            for ( int k = 1 ; k <= n ; k ++ ) {
                //cout << k << endl ;
                dp[ s | lines[ j ][ k ] ] = min ( dp[ s | lines[ j ][ k ] ] ,dp[ s ] + 1 ) ;
            }
        }
        printf ( "%d\n" , dp[ ( 1 << n ) - 1 ] ) ;
    }
    return 0 ;
}