BUPTテニステスト試合II Bクレーン

この問題は当時私が直接裸で探したが、実は考えていたはずの15!きっとタイムアウトでしょう...
しかし、この問題は当時LGもやったので、彼は通り過ぎて、彼のコードを見て、使った状態で圧縮しました.
後で状態圧縮の論文を見て、理解して、今日更に彼のコードを見てとても分かりました==.基本的には一度写して、小さな場所を変えました.
ビット演算の状態圧縮は、すべての状態を考慮したことに相当し、この問題も2^15の状態なので、時間複雑度比N!小さくなったら、一つの状態を列挙すればいいです.
つまり2つの円を列挙して、交差するかどうかを見て、とても不思議です.2^N*Nの時間的複雑さ.
BUPTにメールを送りました.この問題は彼らのテーマのリストを追加していません...検証していませんね.の
でも正しいと思うよ~~
P.S.BUPTに問題が加わった~~~へへへ

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

using namespace std;

const int MAX = 20;
struct point {
	int x, y, r;
	void get()
	{
		scanf("%d%d%d", &x, &y, &r);
	}
};
point p[MAX];
long long disp2p(point a,point b)
{
	return (a.x - b.x)*1ll*(a.x - b.x) + (a.y - b.y)*1ll*(a.y - b.y);
}
bool inst(int x, int y)
{
	return disp2p(p[y], p[x]) <= (p[y].r + p[x].r)*1ll*(p[y].r + p[x].r);
}

bool BIN(int i, int n)
{
	FOR(j, 0, n)
		FOR(k, j+1, n)
			if( ( (1<<j) & i ) && ((1<<k) & i ) )
				if( inst(j, k) )  	//   
					return false;
	return true;
}
int solve(int n)
{
	int ans, mmax = 0;
	FOR(i, 0, 1<<n)
	{
		ans = 0;
		bool f = BIN(i, n);
		if( f )
			FOR(k, 0, n)
				if( (1<<k) & i )
					ans += p[k].r * p[k].r;
		mmax = max(mmax, ans);
	}
	return mmax;
}

int main()
{
	int n, ncases;

	scanf("%d", &ncases);
	
	while( ncases-- )
	{
		scanf("%d", &n);
		FOR(i, 0, n)
			p[i].get();
		
		int ans = solve(n);
		printf("%d
", ans);
	}

return 0;
}