首页 > 其他分享 >hdu4739 Zhuge Liang's Mines --状压dp

hdu4739 Zhuge Liang's Mines --状压dp

时间:2022-12-06 20:40:08浏览次数:59  
标签:node Node -- 状压 ++ int Zhuge include dp


原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=4739​


题意:n个点,求出可以组成的最多的正方形的点数,要求每个点只能用一次,且正方形边平行坐标轴。


分析:把所有点组合,判断是否是平行于坐标轴的正方形,是的话,保存,然后遍历。


#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

struct Node
{
int x, y;
};

int n;
Node node[25];
int dp[1 << 20];
int sta[5000];

bool cmp(Node a, Node b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}

/* 判断是否是平行于坐标轴的正方形 */
bool judge(Node a, Node b, Node c, Node d)
{
if (a.x == b.x&&c.x == d.x&&a.x != d.x)//平行坐标轴
{
if (a.y == c.y&&b.y == d.y)//直角
{
if (b.y - a.y == c.x - a.x)//判断四边相等
{
return 1;
}
}
}
return 0;
}

int main()
{
while (scanf("%d", &n) && n != -1)
{
memset(dp, 0, sizeof(dp));

for (int i = 0; i < n; i++)
scanf("%d %d", &node[i].x, &node[i].y);

sort(node, node + n, cmp);

int num = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
for (int k = j + 1; k < n; k++)
{
for (int l = k + 1; l < n; l++)
{
//cout << i << " " << j << " " << k << " " << l << endl;
int index = (1 << i) | (1 << j) | (1 << k) | (1 << l);
if (judge(node[i], node[j], node[k], node[l]))
sta[num++] = index;
}
}
}
}

//cout << num << endl;
for (int i = 0; i < (1 << n); i++)
for (int j = 0; j < num; j++)
if ((i&sta[j]) == 0)
dp[i | sta[j]] = max(dp[i | sta[j]], dp[i] + 4);

printf("%d\n", dp[(1 << n) - 1]);
}
return 0;
}





标签:node,Node,--,状压,++,int,Zhuge,include,dp
From: https://blog.51cto.com/u_11937443/5916595

相关文章

  • hdu5135 Little Zu Chongzhi's Triangles --状压dp
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=5135​​题意:n根木棒,组成若干三角形,求最大面积和。分析:把所有木棒升序排序,可以组成三角形所有的的组合利用位运算......
  • poj3420 Quad Tiling--状压dp+矩阵快速幂
    原题链接:​​http://poj.org/problem?id=3420​​题意:一个4*n的格子,一个1*2的填充,求填充方式。分析:n最大是10^9,比较大,用矩阵快速幂优化速度。#define_CRT_SECURE_NO_DEPREC......
  • poj 2663 Tri Tiling--状压dp
    原题链接:​​http://poj.org/problem?id=2663​​题意:一个3*n的表格,用一个1*2的方块填充,在填满的情况下,一共多少种填充方式。#define_CRT_SECURE_NO_DEPRECATE#include<ios......
  • poj2411 Mondriaan's Dream--状压dp
    原题链接:​​http://poj.org/problem?id=2411​​.题意:一个n*m的方格,给定一个1*2的方块,要求用这个方块填充方格,填满,一共多少种填充方法。分析:对于一行的某一列来说,该列有三......
  • poj 3254 Corn Fields--状压dp入门
    原题链接:​​http://poj.org/problem?id=3254​​题意:给出一个n行m列的草地,1表示肥沃,0表示贫瘠,现在要把一些牛放在肥沃的草地上,但是要求所有牛不能相邻,问你有多少种放法。分......
  • hdu4705 Y--树形dp
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=4705​​题意:一棵树,求三个点不在一条线的个数。分析:注意,反过来求,求出三个点在一条线的个数,最后总数减去在一条线的......
  • hdu3899 JLUCPC--树形dp(好题)
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=3899​​题意:给定n个点,每个点的人数,n-1条边和边权。选取任意一点u,然后让所有人都移动到u点,问最小的移动距离和是多......
  • UVALive 2038 Strategic game--树形dp
    原题链接:​​http://vjudge.net/problem/UVALive-2038​​题意:一棵树,n个点,0为根,求最少的点可以覆盖所有边。分析:dp[u][0]表示u点不选;dp[u][1]表示该点选择。#defin......
  • UVALive 4015 Caves--树形dp
    原题链接:​​http://vjudge.net/problem/UVALive-4015​​题意:n个部落,编号0到n-1,n-1条路连接n个部落,连成一棵树,机器人从树根出发,问在最多走x米最多经过多少部落。分析:dp[i......
  • 语言并不是使用Serverless跨不去的门槛
    语言并不是使用Serverless跨不去的门槛我们在使用Serverless进行开发的时候,你有没有想过这个问题,Serverless支持Java,Python,NodeJS等一些主流语言,那么碰到我们不支持的语言......