Dilworth 定理

Standard

今天想起高中搞算法竞赛的时候的一个题目:NOIP1999导弹拦截。当时并不明白第二问的做法为什么是正确的,现在又看了一遍离散数学书后总算知道了。这个问题的第二问是要求出一个序列最少能被多少个不上升序列覆盖,比如\((1,4,3,2,6,7)\)可以分解成\((1,4,6,7),(3),(2)\)这三段不上升序列,并且这是最少的划分,而通过Dilworth定理就可以得出这最少划分数和这个序列的最长不升子序列长度的关系,比如,在刚才这个例子中\((4,3,2)\)是最长不升子序列,它的长度也是3。

Dilworth定理更加一般的阐述了这种对应的关系,接下来介绍这个定理:

首先,定义“\(\leq\)”是一个偏序关系(例如集合的包含关系、正整数的整除关系都是偏序关系),下面的例子阐述的是\(A=(1,2,3,5,6,10,15,30,60)\),\(B=(1,2,3,4,6,8,12,24)\)以及\(C=A\cup B\)整除关于整除关系的哈斯图(从下往上看,每条连线上面的元素意味着能被下面的元素整除,并且传递关系被省略不写)

哈斯图

描述整除关系的哈斯图(图片来源

在A集合中\((30,15,5,1)\)之中任何两个元素都是“可比的”(在这个例子当中意味着一方可以被另一个整除,比如15能被5整除),我们把元素集合的这样一个子集称之为“”。而5不能被3、2整除,反之也不能,所以5和3、2是不可比的,一个反链指的是一个任何两个不同的元素都不可比的集合,比如在A中\({5,3,2}\)就是一个反链(实际上也是A种最长的反链,另外\({15,10,6}\)也是最长的反链)。集合的一个链划分指的是将集合分成若干个交为空的链,并且使得它们的并是整个集合,比如对于A集合来说\((1,5,10,30),(3,15),(2,6)\)构成了一个链划分(这个划分中链的个数是所有划分中最少的)

Dilworth定理:集合中 最长的 反链长度  等于  把集合 链划分 的 最小 链个数。

在C集合中,{8, 10, 12, 15}是个最长的反链,而C可以被链划分成 { {5, 15}, {1, 10, 30, 60}, {3, 6, 12}, {2, 4, 8, 24} }。

另外Dilworth定理也意味着:

集合中 最长的 链长度  等于  把集合 反链划分 的 最小 反链个数。(反链划分的定义和链划分类似)

现在回头看把一个序列划分成最少的不上升子序列的问题——显然,“小于等于”和“大于”关系在某全序集合A(全序意味着集合中任意元素可比)上是互补的,也就是说在偏序集\(<A,\leq>\)中的最大反链长其实就是\(<A,>>\)中的最大链长,也就是说要求出不升序划分(链最少的不升序链划分)就等于是求最长上升序列的长度!于是问题就解决了。

练习题

 

最小费用最大流代码

Standard
class Node{
public:
	int f,n,c,w;
	Node *pr,*inv;
}*Adj[Nx];
inline void add(int u,int v,int c,int w){
Node *p=new Node;
	p->f=u,p->n=v,p->c=c,p->w=w;
	p->pr=Adj[u];
	Adj[u]=p;
	  p=new Node;
	p->f=v,p->n=u,p->c=0,p->w=-w;
	p->pr=Adj[v];
	Adj[v]=p;
	
	Adj[v]->inv=Adj[u];
	Adj[u]->inv=Adj[v];
}
Node *pr[Nx];
class Queue{
public:
	int li[Nx*100],h,t,MC[1000],Min[1000];
	bool Inq[Nx];
	bool spfa(){
		h=t=1;
		memset(MC,15,sizeof(MC));
		memset(Min,15,sizeof(Min));
		MC[S]=0;
		li[t++]=S;
		Inq[S]=true;
		while(hpr)
				if(p->c>0 && MC[p->n]>MC[H]+p->w){
					pr[p->n]=p;
					MC[p->n]=MC[H]+p->w;
					Min[p->n]=min(Min[H],p->c);
					if(!Inq[p->n]){
						Inq[p->n]=true;
						li[t++]=p->n;
					}
				}
			Inq[li[h++]]=false;
		}
		if(MC[T]==Inf)
			return false;
	Node *now=pr[T];
		MaxFlow+=Min[T];
		while(1){
			Cost+=Min[T]*now->w;
			now->c-=Min[T];
			now->inv->c+=Min[T];
			if(now->f==0)
				break;
			now=pr[now->f];
		}
		return true;
	}
}Q;

[Contest Hunter]Katharon # 1 题解

Standard

比赛链接

内容提要:

  • Preprefix Sum
    红果果的线段树,只是交的时候用iostreamT了
  • 防御准备
    斜率优化动态规划,注意凸包的维护顺序
  • 国王奇遇记
  • 千钧一发
  • 决战

Preprefix Sum

在线段树中加入LSum标记表示前缀和,然后随便搞。

防御准备

1D/1D动态规划优化,容易得到决策是单调递减的,我采用的是斜率优化时间复杂度O(N),和经典问题不同的地方是这个问题动态维护凸包是逆时针的,而经典问题是顺时针的,所以二者用叉积判断方位会恰恰相反(只考虑两条边,如果考虑三条边的方位就没有变化)

f[i]=min( f[j]+ Cost(i,j) ) + A[i](A[i]是修建防御塔的费用)

经过转化得到
f[i]=min(↓↓↓↓) + A[i]
f[j]+((j-i)^2-j+i)/2
f[j]+(j^2-2ij+i^2-j+i)/2
f[j]+(j^2-j -2ij +i^2+i)/2
f[j]+(j^2-j)/2 -ij  +(i^2+i)/2

设Y=f[j]+(j^2-j)/2 X=j ,然后。。。就是经典问题,具体教程见《1D/1D动态规划优化初步》

国王奇遇记

千钧一发

决战

[APIO2012] 派遣

Standard

去年此时听说了左偏树,以为会很大神,现在看看,发现也是蛮简单的.

关于左偏树和可合并堆,网上有很多的资料,可自行查阅.

题目  题目大意:

给你一棵有根树,每个节点有两个属性:花费和领导力,现在要求选任意一棵子树中的点,使得(这棵子树中尽量选点而总花费不超过M能选的最多的点)*(这颗子树树根的领导力)最大

枚举树根是很显然的,但是选点呢?

容易想到把树中的点按照花费排序,然后尽量取小的,这样一定是最多的,但是这样怎么做呢?

每个节点开一棵左偏树,注意是大根堆,如果是小根堆尽量选小的点时需要删除,维护起来很麻烦,而大根堆的话,只需要比较如果堆的总和比M大,显然最大的那个点是没用的,所以就把它删掉,就这样删删删直到堆的和小于等于M,然后堆的大小就是最优值,每次递归回来合并一下就行了。

还有要注意一点,有两个点的数据是个 链+杂边 深度是99999,栈里面一定要少放东西(尤其是STL的东西),否则会爆栈爆到死。

网络流问题类型

Standard

最大流问题

最小费用最大流

有容量下限的网络流

平面图求最小割

BJOI2006 狼抓兔子,NOI2010 海拔

最大权闭合子图

代表的问题有:太空飞行计划,NOI2009 植物大战僵尸

关于闭合图等等的概念详见国家集训队员胡博涛2007年的论文

做法:

  1. 新建两点s,t,分别表示源和汇,从s向所有点权为正的点连一条流量为该权的边,从所有点权为负的点连一条流量为 负该权 的边,我们要求的最优值就是 所有正值-新图从s到t的最大流

求最大权闭合子图可以这么理解:

  • 一个闭合子图对应一个“割”划分的S集合(包含源点的集合)
  • 最大流求出的是 不再最优的S集合中的正权值和 – 在最优的S集合中的负权值和
  • 我们要求 在最优的S集合中的(正权值和+负权值和)
  • 所以我们要求的是 所有正权值和-最大流

用网络流算法求解线性规划问题

代表的问题有:NOI2008志愿者招募  ZJOI2013防守战线

二分图最大匹配

二分图 最大点权独立集/最小点权覆盖集

hehe
hehe

[NOI2010] 海拔

Standard

题目描述在这里

别人的题解

和这个问题类似的有:

看到这个问题的本质后就很简单了,注意,用SPFA求最短路的话会慢一些(如果是用数组存储广搜队列会爆掉),所以建议用 堆优化的Dijkstra(用STL的容器可以快速实现,详见这篇文章

[NOI2005] 聪聪和可可

Standard

计算数学期望的动态规划,题目描述有以下要注意的:

  • “灰姑娘想知道,平均情况下,聪聪几步就可能吃到可可”背后的意思就是所有可能的长度之和除以可能的路径数,也就是数学期望(∑Lenth*probability)
  • 聪聪沿着最短路每次走两步,可可走一步或者不走,说明路径长度是有限的

思考聪聪在i吃掉在j的可可的数学期望(记为P0)由哪些部分组成(聪聪总是在跑,可可就不一定):

  1. 可可呆滞,聪聪移动之后吃掉可可的期望记为P1
  2. 可可随机行走,聪聪移动之后吃掉可可的期望记为P2

那么P0=(P1+P2)/(度数+1) +1

具体实现:用f[i][j]表示聪聪在i可可在j时聪聪吃掉可可的期望,聪聪先走,记T=Next[Next[i][j]][j] (即聪聪按照最短路走两步到达的点)

f[i][j]=(f[T][j]+∑f[T][k])/(Deg[j]+1)  + 1

Deg[j]是点j的度数,k是和j相邻的点

 

[ZJOI2013]蚂蚁寻路

Standard

题目描述

首先,抽取有用的信息:

  • 按照右右左左。。右右右的顺序生成的图形一定由的是一高一低一高一低的同底的小矩形拼接而成
  • 蚂蚁可以从任意的点出发

于是这个问题就变成了:一定一个特别的图形,求覆盖矩形的最大权值和,这里矩形的权值和就是矩形上所有格子的权值和

下面有动态规划算法:

用一个4维的数组(i,j,k,h)表示右下角坐标为(i,j),在目标图形中是第k个子矩形,左上角为(h,j)的矩形及之前图形组成的图案的最大权值和

状态转移方程:(i,j,k,h)=max((i,j-1,k,h),(i,j-1,k-1,l)) (l>h(偶数),l<h(奇数))

这样总时间复杂度是O(N^3 × M×K)的,显然会超时,考虑到max中后一项是O(N)的而且仅仅是求max,所以可以用am表示l>h的最大值,bm表示i<h的最大值,并把他们存起来就行了(即再开两个4维数组)

一定注意边界条件,用f表示状态的4元组,那么(am,bm,f)[i][0][k][h]=-Infinite,即这些是无效状态。

进一步的,对于i不同的两个状态显然没有什么关系,所以空间上我们可以忽略i这一维,即降成3元祖

代码:

#include 
#include 
#define F_I "zjoi13_ant.in"
#define F_O "zjoi13_ant.out"
using namespace std;
ifstream fin(F_I);
ofstream fout(F_O);
typedef long long ll;
const ll Nx=202;
ll Inf=1234567890;
ll R,C,RecN,Map[Nx][Nx],RS[Nx][Nx],Sum[Nx][Nx],Answer;
ll f[Nx][30][Nx],am[Nx][30][Nx],bm[Nx][30][Nx];
void init(){
ll i,j;
	Inf*=Inf;
	fin>>R>>C>>RecN;
	RecN=RecN*2+1;
	for(i=1;i<=R;i++)
		for(j=1;j<=C;j++){
			fin>>Map[i][j];
			Sum[i][j]=Sum[i-1][j]+Map[i][j];
		}
}
void dp(){
ll i,j,k,h;
//	for(i=1;i<=R;i++)
		for(j=1;j<=R;j++)
			for(k=1;k<=RecN;k++)
				f[0][k][j]=bm[0][k][j]=am[0][k][j]=-Inf;
	Answer=-Inf;
	for(i=1;i<=R;i++)
		for(j=1;j<=C;j++){
			for(k=1;k<=RecN;k++){
				for(h=i;h>=1;h--)
					if(k%2)
						f[j][k][h]=max(f[j-1][k][h],bm[j-1][k-1][h])+Sum[i][j]-Sum[h-1][j];
					else
						f[j][k][h]=max(f[j-1][k][h],am[j-1][k-1][h])+Sum[i][j]-Sum[h-1][j];
				am[j][k][1]=-Inf;
				for(h=2;h<=i;h++)
					am[j][k][h]=max(am[j][k][h-1],f[j][k][h-1]);
				bm[j][k][i]=-Inf;
				for(h=i-1;h>=1;h--)
					bm[j][k][h]=max(bm[j][k][h+1],f[j][k][h+1]);
			}
			Answer=max(Answer,max(am[j][RecN][i],f[j][RecN][i]));
		}
	fout<<Answer<<endl;
}
int main(){
	init();

	dp();

	fin.close();
	fout.close();
    return 0;
}