#include<iostream>

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<cctype>
#include<bitset>
using namespace std;

const int tt[61][6][2] =
{
	{{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 0}, {0, 1}, {1, 0}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 0}, {0, 1}, {1, 1}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 0}, {1, 0}, {1, 1}, {0, 0}, {0, 0}},
	{{3, 0}, {0, 1}, {1, 0}, {1, 1}, {0, 0}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 2}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {1, 1}, {1, 2}, {0, 0}},
	{{4, 0}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {2, 0}, {0, 1}, {0, 0}},
	{{4, 0}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {0, 0}},
	{{4, 0}, {0, 0}, {0, 1}, {1, 1}, {2, 1}, {0, 0}},
	{{4, 0}, {0, 1}, {1, 1}, {2, 1}, {2, 0}, {0, 0}},	
	{{4, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {0, 0}},		
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {2, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 2}, {2, 2}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}},
	{{5, 0}, {0, 2}, {1, 2}, {2, 0}, {2, 1}, {2, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 2}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 1}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 2}},		 
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {1, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {2, 1}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {1, 0}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {2, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 2}},
	{{5, 0}, {0, 0}, {0, 2}, {1, 0}, {1, 1}, {1, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 1}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {0, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {1, 2}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {1, 1}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}},
	{{5, 0}, {1, 0}, {0, 1}, {0, 2}, {1, 1}, {1, 2}},
	{{5, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 1}, {1, 2}, {1, 3}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {0, 2}, {0, 3}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {2, 0}, {3, 0}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {3, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {1, 1}, {2, 1}, {3, 1}},
	{{5, 0}, {0, 1}, {1, 1}, {1, 0}, {2, 0}, {3, 0}},
	{{5, 0}, {0, 1}, {1, 0}, {1, 1}, {1, 2}, {2, 1}},
	{{5, 0}, {0, 1}, {0, 2}, {1, 0}, {2, 0}, {1, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}},
	{{5, 0}, {0, 0}, {1, 0}, {1, 1}, {2, 1}, {2, 2}},
	{{5, 0}, {0, 2}, {1, 1}, {1, 2}, {2, 0}, {2, 1}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 0}},
	{{5, 0}, {0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 3}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 0}},
	{{5, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {0, 3}},			 
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {0, 1}},
	{{5, 0}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {3, 1}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {0, 0}},
	{{5, 0}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {3, 0}}
};

const int t[13][2] = 
{
	{0, 0}, {1, 4}, {5, 6}, {7, 14}, {15, 15}, {16, 19}, {20, 27}, 
	{28, 31}, {32, 39}, {40, 47}, {48, 48}, {49, 52}, {53, 60}
};
			  
const int ft[61] = 
{
	0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 5, 5, 5, 5, 
	6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 
	9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12
};

const int tooo[78] = 
{
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12
};
	
char m1[12][12];

bool use[11][11];
bool choose[3005];

int d[350005], u[350005], r[350005], l[350005], col[350005], row[350005], size[105];
int done[13];
int mtx[3005][70];
int btl[11][11], ltb[60][2], ctl[100], map[11][11];
int h, z, node;
int xx[3005], yy[3005], nn[3005];
int num, que[100];

void init()
{
	memset(done, 0, sizeof(done));
   freopen("zhzyx.in", "r", stdin);
	for (int i = 1; i <= 10; i++) 
	{
		gets(m1[i]);
		for (int j = 1; j <= i; j++)
		{
			map[i][j] = tooo[(int)m1[i][j - 1]];
			if (map[i][j]) use[i][j] = 1, done[map[i][j]] = 1;
		}
	}
}

bool check(int k, int x, int y)
{
	for (int i = 1; i <= tt[k][0][0]; i++)
		if (use[x + tt[k][i][0]][y + tt[k][i][1]] || x + tt[k][i][0] < y + tt[k][i][1] || x + tt[k][i][0] > 10) return 0;
	return 1;
}

void prepare()
{
	h = 0;
	for (int i = 1; i <= 10; i++)
		for (int j = 1; j <= i; j++)
			if (!use[i][j])
				btl[i][j] = ++h;
	for (int i = 1; i <= 12; i++)
		if (!done[i])
			ctl[i] = ++h;
	z = 0;
	memset(mtx, 0, sizeof(mtx));
	for (int i = 1; i <= 12; i++)
		if (!done[i])
			for (int j = t[i][0]; j <= t[i][1]; j++)
				for (int x = 1; x <= 10; x++)
					for (int y = 1; y <= x; y++)
						if (check(j, x, y))
						{
							mtx[++z][ctl[i]] = 1;
							xx[z] = x; yy[z] = y; nn[z] = j;
							for (int k = 1; k <= tt[j][0][0]; k++)
								mtx[z][btl[x + tt[j][k][0]][y + tt[j][k][1]]] = 1;
						}
}


void build(int line)
{
	for (int i = 1; i <= num; ++i, ++node)
	{
		int p = que[i];
		size[p]++;
		row[node] = line;
		col[node] = p;
		d[node] = p;
		u[node] = u[p];
		d[u[node]] = node;
		u[d[node]] = node;
		if (i == 1) r[node] = node, l[node] = node;
		else
		{
			l[node] = node - 1;
			r[node] = node - i + 1;
			l[r[node]] = node;
			r[l[node]] = node;
		}
	}
}

void addp()
{
	node = h + 1;
	memset(r, -1, sizeof(r));
	memset(l, -1, sizeof(r));
	memset(u, -1, sizeof(r));
	memset(d, -1, sizeof(r));
	for (int i = 1; i <= h; i++)
		r[i - 1] = i, l[i] = i - 1, u[i] = i, d[i] = i, row[i] = 0, col[i] = i, size[i] = 1;
	r[h] = 0; l[0] = h; u[0] = 0; d[0] = 0; col[0] = 0; row[0] = 0;

	for (int i = 1; i <= z; ++i)
	{
		num = 0;
		for (int j = 1; j <= h; ++j)
			if (mtx[i][j]) que[++num] = j;
		build(i);
	}
}

void remove(int k)
{
	r[l[k]] = r[k]; l[r[k]] = l[k];
	for (int i = d[k]; i != k; i = d[i])
		for (int j = r[i]; j != i; j = r[j])
		{
			u[d[j]] = u[j];
			d[u[j]] = d[j];
			size[col[j]]--;
		}
}
void resume(int k)
{
	for (int i = u[k]; i != k; i = u[i])
		for (int j = l[i]; j != i; j = l[j])
			size[col[u[d[j]] = d[u[j]] = j]]++;
	l[r[k]] = r[l[k]] = k;
}
bool dfs(int k)
{
	if (r[0] == 0) return 1;
	int mini = INT_MAX, pos = 0;
	for (int i = r[0]; i != 0; i = r[i])
		if (size[i] < mini) mini = size[i], pos = i;
	remove(pos);
	for (int p = d[pos]; p != pos; p = d[p])
	{
		choose[row[p]] = 1;
		for (int q = r[p]; q != p; q = r[q]) remove(col[q]);
		if (dfs(k + 1)) return 1;
		choose[row[p]] = 0;
		for (int q = l[p]; q != p; q = l[q]) resume(col[q]);
	}
	resume(pos);
	return 0;
}
void fill(int k, int x, int y)
{
	for (int i = 1; i <= tt[k][0][0]; i++)
		map[x + tt[k][i][0]][y + tt[k][i][1]] = ft[k];
}

void outit()
{
   freopen("zhzyx.out", "w", stdout);
	if (dfs(1))
	{
		for (int i = 1; i <= 3005; i++) if (choose[i]) fill(nn[i], xx[i], yy[i]);
		for (int i = 1; i <= 10; i++)
		{
			for (int j = 1; j <= i; j++) printf("%c", (char)map[i][j] + 64);
			printf("\n");
		}
	}
	else cout<<"No solution"<<endl;
	exit(0);
}

int main()
{
   init();
	prepare();
	addp();
	outit();
   return 0;
}

看了好久好久，终于看懂了。

于是果断发一篇。 尽量讲得易懂点吧。

 

【第一篇学术讨论文~~】

 

首先，二元关系的定义：

设S是一个非空集合，若R是关于S的有序元素对的一个关系，即对S中任意一个有序元素对（a，b），我们总能确定a与b是否满足条件R，就称R是S的一个关系（relation），又由于他是建立在二元（即S中任意两个元素）之上的，因此也称为二元关系。

 

然后，偏序关系的定义：

偏序关系是在集合X上的二元关系 “≤”（这只是个抽象符号，其内涵是由你定义的，并不是“小于或等于”），它满足自

反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:

自反性：a≤a; 【自我反对称，大概就是这个意思吧】

反对称性：如果a≤b且b≤a，则有a=b;

传递性：如果a≤b且b≤c，则a≤c 。

偏序关系与一般二元关系的区别，也就在于其三个性质

例如集合S={a1，a2...an},设其每一个表示一个人

如果二元关系为【a为男，b为女】，那么这个二元关系显然不符合第一条性质自反性，因此这是二元关系而不是偏序关系。

又如二元关系为【a是b的亲戚】，那么这个二元关系显然不符合第二条性质反对称性，因此这是二元关系而不是偏序关系。

又如二元关系为【a认为b是好人】，那么这个二元关系显然不符合第三条性质传递性，因此这是二元关系而不是偏序关系。

于是偏序关系介绍到这里。

 

偏序集：也就是带有偏序关系的集合。偏序集可以表示为集合与偏序关系的整体，记为（X,≤）【其中X为集合，≤为偏序

关系】。对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比，这就是可比性的定义。

一个链C是X的一个子集，它的任意两个元素都可比。

 

极小元：在X中，对于元素a，如果任意元素b，由b≤a得出b=a，则称a为极小元。很容易看出，在链中，极小元可以看做链的初始元，

有点类似于拓扑图中没有前驱的点。

 

相对应的，一个反链A是X的一个子集，它的任意两个元素都不能进行比较。

 

至于最大链，最大反链，就是集合中最长【即包含元素最多】的链、反链的意思了。

而最大反链数，就是一个集合最多可以划分成多少个反链。最长反链长度就是最长反链中元素个数。

下面，两个重要定理，有关dilworth：

定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则r为X的最大反链数。

对偶定理:定理2：对于一个偏序集，其最少反链划分数等于其最长链的长度。这就是Dilworth定理。

 

定理2证明：首先设p为最少反链划分个数。

因为划分成反链以后，反链中间任何两个元素都不可比，因此最大链中的元素必须全部分开，因此必然有p大于等于r。【为

了避免与偏序关系的符号重复，在此使用中文“大于等于”等等进行说明】

下面证明r大于等于p：

设X1=X，考虑这样一种操作，第i次操作从Xi中拿出其所有最小元的集合，设为Ai。那么总存在k，使得第k次操作前的Xk为非

空集合而X（k+1）为空集。此时每次拿出的最小元集合顺序为A1,A2...Ak ，易知这就是X种反的一链划分。由于每次取出的

都是最小元，由最小元的定义我们可以得知，对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。由此A1...Ak中一定

存在一条链【有人说有反例，哼哼，你们试试吧】。又因为r是最长链长度，因此r大于等于k，又易知k要大于等于p，因此r

大于等于p。

 

综上所述，r=p，得证。

 

有了这个，定理1也就很好证明了【过程类似嘛】，请读者自行证明。【其实是因为我很懒，嘿嘿】

 

现在我们再来看拦截导弹

【Description 描述】

 

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到

达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶

段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截

所有导弹最少要配备多少套这种导弹拦截系统。

【Input 输入文件】missile.in

单独一行列出导弹依次飞来的高度。

【Output 输出文件】missile.out

两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数

【Sample Input输入样例】

389 207 155 300 299 170 158 65

【Sample Output输出样例】

6

2

 

第一问很好做，最长不上升子序列。

第二问，哈哈，往上翻~上翻~，这不是求最少链划分数嘛？这不是反的Dilworth吗？

那也就是说，既然最少反链划分数等于其最长链的长度，那最少链划分数不就是最大反链长度吗？

恭喜你答对了。于是问题一下子转化成了求最大反链长度。反过来dp一次，马上ac

 

注意一点，由于在此题中链的定义是“a≤b→a出现在b之前且a大于等于b”

因此反链是“a出现在b前且a小于b（不能等于啊！）”

 

欢迎大神鄙视...

 

其实纠结了很久，关于究竟在哪个网站写blog【各大神牛都有啊！！！！】。

 

其实原来是想效仿各位神牛去csdn的，但是看到is-programmer的域名...果断决定了

 

总之嘛...成立仪式~

 

 

 

 

以后就要开始在这上面作总结了,加油！