hdu4739 Zhuge Liang's Mines 状态压缩dp，0-1双肩包

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);
    }
}