(匹配)Dolls --HDU --4160

news/2024/11/13 2:35:36/

链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4160

 

 

代码:

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;#define N 550/// 匹配
struct node {int w, l, h;}a[N];int G[N][N], used[N], p[N], n;int cmp(node n1, node n2)
{if(n1.w!=n2.w)return n1.w > n2.w;if(n1.l!=n2.l)return n1.l > n2.l;return n1.h > n2.h;
}bool Find(int u)
{for(int i=1; i<=n; i++){if(!used[i] && G[u][i]){used[i] = 1;if(!p[i] || Find(p[i])){p[i] = u;return true;}}}return false;
}int main()
{while(scanf("%d", &n), n){int i, j;memset(a, 0, sizeof(a));memset(G, 0, sizeof(G));for(i=1; i<=n; i++)scanf("%d%d%d", &a[i].w, &a[i].l, &a[i].h);sort(a+1, a+n+1, cmp);for(i=1; i<=n; i++){for(j=1; j<i; j++){if(a[i].w<a[j].w && a[i].l<a[j].l && a[i].h<a[j].h)G[i][j]=1;}}int ans = 0;memset(p, 0, sizeof(p));for(i=1; i<=n; i++){memset(used, 0, sizeof(used));if(Find(i))ans++;}printf("%d\n", n-ans);}return 0;
}

 

转载于:https://www.cnblogs.com/YY56/p/4731949.html


http://www.ppmy.cn/news/325681.html

相关文章

2015.9.11模拟赛 codevs 4160【会玩的】

题目描述 Description hzwer真的很会玩啊…他有一个n*m的方格&#xff0c;每次可以给方格添加一整行或一整列&#xff0c;但是不能删除。现在他想要让总格子数超过k个&#xff0c;但是又想让总格子数尽可能小。请找出这时的n,m。如果有多解&#xff0c;输出任意一种方案。 输入…

洛谷P4160 生日快乐

这道题是标准的暴力深搜&#xff0c;思想如下&#xff1a; 因为每一块蛋糕的面积都要相同&#xff0c;因此切分成最小块的蛋糕的长度应该为x/n的整数倍&#xff0c;如图&#xff1a; 这样&#xff0c;一块蛋糕就被分成了两部分&#xff0c;分别是我们所需的最小单元的 i i i…

BZOJ1024洛谷P4160 [SCOI2009]生日快乐

搜索等分点&#xff0c;看在哪部分找就行了 代码 //By AcerMo #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const double M1e97; int n; double a,b; double minn(double x,double y) {if (x&…

洛谷 P4160 [SCOI2009]生日快乐

PS&#xff1a;如果读过题了可以跳过题目描述直接到题解部分 提交链接&#xff1a;洛谷 P4160 [SCOI2009]生日快乐 题目 题目描述 windy 的生日到了&#xff0c;为了庆祝生日&#xff0c;他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。 现在包括 windy&#xff0c…

BZOJ.4160.[NEERC2009]Exclusive Access 2(状压DP Dilworth定理)

BZOJ DAG中&#xff0c;根据\(Dilworth\)定理&#xff0c;有 \(最长反链最小链覆盖\)&#xff0c;也有 \(最长链最小反链划分数-1\)&#xff08;这个是指最短的最长链&#xff1f;并不是很确定-&#xff09;&#xff0c;即把所有点划分成最少的集合&#xff0c;使得集合内的点两…

luogu P4160 [SCOI2009]生日快乐

传送门 考虑因为每个人的蛋糕体积要相等,如果切了一刀,那么要使得分当前蛋糕的人根据分成的两部分蛋糕的体积分成两部分人,所以假设当前有n人,切的这一刀要是在x或y的\(\frac{k}{n}(k\in N_,k\in [1,n])\)处,然后两边分别有\(k\)和\(n-k\)个人分,所以分治做下去救星了 更多内容…

2023-06-11 LeetCode每日一题(从链表中删去总和值为零的连续节点)

2023-03-29每日一题 一、题目编号 1171. 从链表中删去总和值为零的连续节点二、题目链接 点击跳转到题目位置 三、题目描述 给你一个链表的头节点 head&#xff0c;请你编写代码&#xff0c;反复删去链表中由 总和 值为 0 的连续节点组成的序列&#xff0c;直到不存在这样…

[BZOJ]4160: [Neerc2009]Exclusive Access 2 状压DP+Dilworth定理

Description 给出 N 个点M 条边的无向图&#xff0c;定向得到有向无环图&#xff0c;使得最长路最短。 N ≤ 15, M ≤ 100 Solution 大家都知道Dilworth定理的其中一个内容&#xff1a;最小路径覆盖最长反链。 实际上与之相似的是&#xff1a;最长路最小反链划分数。 这个东…