hdu4739 Zhuge Liang's Mines 状态压缩dp，0-1背包
预处理哪4个点可组成的正方形
dp[i]表示集合i的答案，对于每个i枚举前继状态。或用0-1背包
#include <cstdio>#include <ctime>#include <cstdlib>#include <cstring>#include <queue>#include <string>#include <set>#include <stack>#include <map>#include <cmath>#include <vector>#include <iostream>#include <algorithm>#include <bitset>using namespace std;//LOOP#define FE(i, a, b) for(int i = (a); i <= (b); ++i)#define FED(i, b, a) for(int i = (b); i>= (a); --i)#define REP(i, N) for(int i = 0; i < (N); ++i)#define CLR(A,value) memset(A,value,sizeof(A))//INPUT#define RI(n) scanf("%d", &n)#define RII(n, m) scanf("%d%d", &n, &m)#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)#define RS(s) scanf("%s", s)typedef long long LL;const int INF = 1000000007;const int MOD = 1000000007;const double eps = 1e-10;const int MAXN = 31000;int dp[1 << 21];struct node{ int x, y;}t[25];bool cmp(node a, node b){ if (a.y != b.y) return a.y < b.y; else return a.x < b.x;}inline int dis(int x){ if (x < 0) return -x; return x;}int check(node a1, node a2, node b1, node b2){ if (a1.y == a2.y && b1.y == b2.y && a1.x == b1.x && a2.x == b2.x && dis(a2.x - a1.x) == dis(b2.y - a2.y)) return 1; return 0;}vector<int>s;int n;int ALL;void init(){ s.clear(); REP(i, n) FE(j, i + 1, n - 1) FE(ii , j + 1, n - 1) FE(jj, ii + 1, n - 1) { if (check(t[i], t[j], t[ii], t[jj])) { s.push_back((1 << i) | (1 << j) | (1 << ii) | (1 << jj)); } }}int main(){ while (~RI(n) && n != -1) { ALL = (1 << n) - 1; REP(i, n) RII(t[i].x, t[i].y); sort(t, t + n, cmp); init(); int sn = s.size(); CLR(dp, 0); ///状态压缩// for (int ss = 0; ss <= ALL; ss++)// {// REP(i, sn)// {// if ( (ss & (s[i])) == s[i] )// dp[ss] = max(dp[ss], dp[ss ^ s[i]] + 1);// }// } ///0-1背包 REP(i, sn) for (int ss = ALL; ss >= 0; ss--) { if ( (ss & (s[i])) == s[i] ) dp[ss] = max(dp[ss], dp[ss ^ s[i]] + 1); } printf("%d\n", dp[ALL] * 4); }}