愤怒的小鸟【$DP$优化】

卡常的状压$DP$，愤怒的小鸟。

其实本来是个很水的状压$DP$，但因为最后三个点$n=18$，成功地把我的不可能达到的下界为$\Omega(2^nn^2)$，紧确的上界为$O(2^nn^3)$算法给卡死了$\rm{OTZ}$……

那么这个地方，我定义的状态是$dp_s$表示猪的状态为$s$时的最小鸟个数。那么这个东西转移吧，我想的是枚举每个$1$位，把它当做这次更新（杀死）的猪，然后通过其他的猪转移。对于一组猪确定的一个抛物线，再枚举全部的猪，看看能不能从更小的状态更新。

大概枚举两只猪的复杂度都是$\Theta(n^2)$左右的，然后$\Theta(n)$扫一遍，大概复杂度上界为$O(n^3)$，但是事实上根本不会到这个地步。对于$n=15$的情况还是可以刚一波的。

但是之后就凉凉了，因为它实际只能$get$到$85pts$。

#include <cstdio>

#include <iostream>

#define MAXN 30

#define MAXM 400000

#define Inf 1926081700

using namespace std ; struct Func{ double A, B ;} temp ; int i, j, k ;

int T, t1, t0, dp[MAXM + 1], S0[MAXN], S1[MAXN], N, M ; double X[MAXN], Y[MAXN] ; 

inline Func chk(int A, int B){

	double _x1 = X[A], _sx1 = X[A] * X[A] ;

	double _y1 = Y[A], _sy1 = Y[A] * Y[A] ;

	double _x2 = X[B], _sx2 = X[B] * X[B] ;

	double _y2 = Y[B], _sy2 = Y[B] * Y[B] ;

	return (Func){(_y1 * _x2 - _y2 * _x1)/(_sx1 * _x2 - _sx2 * _x1),  (_y2 * _sx1 - _sx2 * _y1)/(_sx1 * _x2 - _sx2 * _x1)} ;

}

inline bool Calc(Func A, int B){

	return A.A * X[B] * X[B] + A.B * X[B] == Y[B] ;

}

inline void clear(){ fill (dp, dp + MAXM + 1, Inf) ;}

inline void Init(){t1 = 0, t0 = 0, fill (S1, S1 + N + 1, 0), fill (S0, S0 + N + 1, 0) ;}

int main(){

	cin >> T ;

	while (T --){

		clear() ; dp[0] = 0 ;

		cin >> N ; M = (1 << N) - 1 ;

		for (i = 1 ; i <= N; ++ i)

			scanf("%lf%lf", &X[i], &Y[i]) ;

		for (i = 1 ; i <= M ; ++ i){

			Init() ;

			for (j = 0 ; j < N ; ++ j)

				if (1 << j & N) S1[++ t1] = j + 1 ;

				else S0[++ t0] = j + 1 ;

			for (j = 1 ; j <= t1 ; ++ j)

				for (k = 1 ; k < j ; ++ k){

					if ((temp = chk(S1[j], S1[k])).A >= 0) continue ;

					int S = i ;

					S ^= (1 << S1[j] - 1), S ^= (1 << S1[k] - 1) ;

					for (int l = 1 ; l <= t1 ; ++ l){

						if (l == j || l == k) continue ;

						if (Calc(temp, S1[l])) S ^= (1 << S1[l] - 1) ;

					}

					dp[i] = min(dp[i], dp[S] + 1) ;

				}

		}

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

	}

}

我们思考一个剪枝。

我们的最优解实质上是唯一的，此处的唯一指的是$DP$的最优子结构性质。那么我们不妨把转移过程单调起来，而不是让它重复枚举。所以我们要按秩转移，随便从一个开始都行，只要有序、不重复即可。那么不妨从最低位开始。这个东西一开始预处理一遍即可。

于是最终的复杂度就变成了$\Theta(2^nn)$，十分带劲。

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#define MAXN 30

#define t1(i) S1[i][0]

#define min my_min

#define MAXM 400000

#define REG register

#define Inf 1926081700

using namespace std ; double X[MAXN], Y[MAXN] ;

const double eps = 1e-7 ; struct Func{ double A, B ;} F[MAXN][MAXN] ;

int m, i, j, k, l, dp[MAXM + 20], Low[MAXM + 20], B[MAXN][MAXN], N, M ;

inline bool Calc(Func A, int B){

	double T = A.A * X[B] * X[B] + A.B * X[B] ; return (T <= Y[B] + eps & T >= Y[B] - eps) ;

}

inline Func chk(int A, int B){

    double _x1 = X[A], _sx1 = X[A] * X[A], _y1 = Y[A], _sy1 = Y[A] * Y[A] ;

    double _x2 = X[B], _sx2 = X[B] * X[B], _y2 = Y[B], _sy2 = Y[B] * Y[B], TT = _sx1 * _x2 - _sx2 * _x1 ;

    return (Func){(_y1 * _x2 - _y2 * _x1) / TT,  (_y2 * _sx1 - _sx2 * _y1) / TT} ;

}

inline int my_min(int A, int B){ return A & ((A - B) >> 31) | B & (~(A - B) >> 31) ;}

int main(){

//	freopen("angrybird.in", "r", stdin) ;

//	freopen("angrybird.out", "w", stdout) ;

	int T ; cin >> T ; M = (1 << 18) - 1 ;

	/*

	for (int i = 1 ; i <= M ; ++ i)

		for (int j = 0 ; j < 18 ; ++ j)

			if (1 << j & i) S1[i][++ S1[i][0]] = j + 1 ;

	*/

	for(i = 0; i <= M ; ++ i){

		j = 1 ;

    	for ( ; j <= 18 && i & (1 << (j - 1)) ; ++ j) ;

    	Low[i] = j ;

    }

    /*for(i=0;i<(1<<18);i++){ //预处理lowunbit

        int j=1;

        for(;j<=18 && i&(1<<(j-1));j++);

        Low[i]=j;

    }*/

    while (T --){

    	memset(B, 0, sizeof(B)) ;

    	memset(dp, 127, sizeof(dp)) ;

        dp[0] = 0 ; cin >> N >> m ; M = (1 << N) - 1 ;

		for (i = 1 ; i <= M ; ++ i) dp[i] = dp[i - (i & -i)] + 1 ;

        for (i = 1 ; i <= N ; ++ i) scanf("%lf%lf", &X[i], &Y[i]) ;

        for (i = 1 ; i <= N ; ++ i)

        	for (j = 1 ; j < i ; ++ j){

        		if (fabs(X[i] - X[j]) <= eps) continue ;

        	 	F[i][j] = F[j][i] = chk(i, j) ;

				if (F[i][j].A >= -eps) continue ;

        	 	for (int k = 1 ; k <= N ; ++ k)

        	 		if (Calc(F[i][j], k)) B[i][j] = B[j][i] |= (1 << k - 1) ;

			}

        for (i = 0 ; i <= M ; ++ i){

        	j = Low[i] ;

        	dp[i | 1 << (j - 1)] = min(dp[i | 1 << (j - 1)], dp[i] + 1) ;

            for (k = 1 ; k <= N; ++ k) dp[i | B[j][k]] = min(dp[i | B[j][k]], dp[i] + 1) ;

    	}

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

    }

}

巴特西

愤怒的小鸟【$DP$优化】

最新文章

热门文章