|
|
2011年9月17日
题目连接：http://poj.org/problem?id=1065
题目大意：有一堆树，每棵树有两个属性：(w,l)，求把这些树按照某种次序排列后的最小setup time ，
定义当！（ wi < w i+1 && li < li+1)时，消耗一个setup time
(表达的不好，见谅)
分析：
Dilworth定理说的是：对于一个偏序集，其最少链划分数等于其最长反链的长度。 Dilworth定理的对偶定理说的是：对于一个偏序集，其最少反链划分数等于其最长链的长度。Dilworth定理先不证，有空再不上来，其对偶定理证明如下： 设一个偏序集S的最少反链划分数是p，最长链长度是r。 1.先证p≥r。这是显然的，因为最长链长度是r，r个元素中的任意两个都可以比较，因此它们必定两两属于不同的反链，因此反链个数≥r，即p≥r。
2.再证r≥p。设X1=S。找出X1的所有极小元组成集合Z1，将其从X1删之，得到X2，再找出X2的所有极小元组成集合Z2（特别注意Z2中的任何元素a2，在X1中必然存在一个元素a1使得a1≤a2，否则a2可以放到X1中，这与X1的选取矛盾），再将Z2从X2中删除，得到X3，……这样一直下去，总存在一个k使得XK不空但X(K+1)为空。这样便得到一条链a1，a2，a3，……，ak，其中ai属于Xi。由于r是最长链长度，因此r≥k。另一方面，我们也得到了一个反链划分，即X1，X2，X3，……，XK。由于p是最少反链划分，因此k≥p。因此有r≥p。证毕。
这个题目的解就是这个定理证明的过程，
本题直接找最长反链就行了
直接排序方法：
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5010;
int n;
struct Node
{
int l;
int w;
};
Node data[MAXN];
bool visit[MAXN];
bool mcmp(Node a,Node b)
{
if(a.l != b.l ) return a.l < b.l;
else return a.w < b.w;
}
void init()
{
int i;
scanf("%d",&n);
for(i = 0;i < n;i ++)
{
scanf("%d%d",&data[i].l,&data[i].w);
visit[i] = false;
}
sort(data,data+n,mcmp);
}
void work()
{
int tn = n;
int i;
int t = 0;
int j;
int ans = 0;
while(tn > 0 )
{
for(i = 0;i < n;i ++)
{
if(visit[i]) continue;
visit[i] = true;
tn --;
t = i;
j = i+1;
while(j < n )
{
if(!visit[j] && data[t].l <= data[j].l && data[t].w <= data[j].w)
{
visit[j] = true;
tn --;
t = j;
}
j ++;
}
ans ++;
}
}
printf("%d\n",ans);
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas -- )
{
init();
work();
}
return 0;
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5010;
int n;
struct Node
{
int l;
int w;
};
Node data[MAXN];
int dp[MAXN];
bool mcmp(Node a,Node b)
{
if(a.l != b.l ) return a.l < b.l;
else return a.w < b.w;
}
void init()
{
scanf("%d",&n);
int i;
for(i = 0;i < n;i ++)
{
scanf("%d%d",&data[i].l,&data[i].w);
}
sort(data,data+n,mcmp);
}
int max(int a,int b)
{
return a > b ? a : b;
}
void work()
{
int i;
dp[0] = 1;
int m = 0;
int j = 0;
for(i = 1;i < n;i ++)
{
dp[i] = 1;
for(j = 0;j < i;j ++)
{
if(data[i].l < data[j].l || data[i].w < data[j].w)
{
dp[i] = max(dp[i],dp[j]+1);
}
}
}
for(i = 0;i < n;i ++)
m = max(m,dp[i]);
printf("%d\n",m);
}
int main()
{
int cas;
scanf("%d",&cas);
while(cas -- )
{
init();
work();
}
return 0;
}
|