Dylan's Blog
Dylan's Blog

白衣苍狗

动态规划——多进程DP

 发布于  收录于 OI

动态规划——多进程DP

luogu1004

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/*
luogu1004
多进程DP 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
void read(T& w)
{
	char r;int f=1;
	for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')r=getchar(),f=-1;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxn=13;
int n;
int a[maxn][maxn];
void input()
{
	read(n);
	int x,y,z;
	for(read(x),read(y),read(z);x||y||z;read(x),read(y),read(z))
	{
		a[x][y]=z;
	}
}

int f[maxn][maxn][maxn][maxn];
void dp()
{
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
	{
		for(int k=1;k<=n;++k) for(int l=1;l<=n;++l)
		{
			f[i][j][k][l]
			=Max(
				Max(
					f[i-1][j][k-1][l],f[i-1][j][k][l-1]),
				Max(
					f[i][j-1][k-1][l],f[i][j-1][k][l-1])
				);
			f[i][j][k][l]+=a[i][j];
			if(i!=k||j!=l)
				f[i][j][k][l]+=a[k][l];
			//cout<<f[i][j][k][l]<<" ";
		}
	}
}
int main()
{
	freopen("luogu1004_1.in","r",stdin);
	//freopen("luogu1004.out","w",stdout);
	input();
	dp();
	printf("%d\n",f[n][n][n][n]);
	return 0;
}

luogu1006

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

/*
luogu1006
多进程DP 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
void read(T& w)
{
	char r;int f=1;
	for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')r=getchar(),f=-1;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxn=53;
int n,m;
int a[maxn][maxn];
void input()
{
	read(n),read(m);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			read(a[i][j]);
		}
	}
}

int f[maxn][maxn][maxn][maxn];
void dp()
{
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
	{
		for(int k=1;k<=n;++k) for(int l=1;l<=m;++l)
		{
			f[i][j][k][l]
			=Max(
				Max(
					f[i-1][j][k-1][l],f[i-1][j][k][l-1]),
				Max(
					f[i][j-1][k-1][l],f[i][j-1][k][l-1])
				);
			f[i][j][k][l]+=a[i][j];
			if(i!=k||j!=l)
				f[i][j][k][l]+=a[k][l];
			//cout<<f[i][j][k][l]<<" ";
		}
	}
}
int main()
{
	freopen("luogu1006_1.in","r",stdin);
	//freopen("luogu1006.out","w",stdout);	
	input();
	dp();
	printf("%d\n",f[n][m][n][m]);
	return 0;
}
阅读全文
动态规划多进程C++OI

堆排序模板

 发布于  收录于 OI
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}

template<typename T>
void shift(T* ary,int k,int f,bool comp(const T& a,const T&b) )
{
	for(int son=k*2;son<=f;k=son,son=k*2)
	{
		if(son+1<=f&&comp(ary[son+1],ary[son]))
			++son;
		if(comp(ary[son],ary[k]))
			Swap(ary[son],ary[k]);
		else break;
	}
}

template<typename T>
void heapSort(T* ary,int l,int r,bool comp(const T& a,const T&b))//r不是超尾而是最后一个元素 
{
	int mid=(l+r)/2;
	for(int i=mid;i>=l;--i)
		shift(ary,i,r,comp);
	for(int i=r;i>=l+1;--i)
	{
		Swap(ary[i],ary[l]);
		shift(ary,l,i-1,comp);
	}
}
阅读全文
OIC++堆排序堆排序

也谈八数码境界

 发布于  收录于 OI

也谈八数码境界

题意

​ 给定一个九宫格起始状态，其中八格放置1~8，有一格为空。空格可以和毗邻的格子交换，一次交换称为一次操作，求达到目标状态所需的最小字典序的最少操作次数及方案。

第一重：BFS+STL

​ 略。

第二重：BFS+CantorHash

Cantor

​ 对所有1~n的排列按字典序进行排序得到一个序列，那么任意一个排列都可以找到在这个序列中的位置（或者说排名），而且这个排名是一一对应的。所以一个排名可以唯一确定一个排列，那么在有关排列的问题里我们就可以利用排名来判重，而不是记下排列中所有的数。 ​ Cantor提供了快速的实现由给定排列计算排名，以及由排名确定排列的方法，称为康托展开。

阅读全文
OIC++搜索CantorBFS

输入输出效率对比

 发布于  收录于 OI

输入输出效率对比

前言

在OI竞赛中，几乎每道题都需要进行文件的读写操作。然而在非常紧的时间限制内，读写的时间也至关重要。目前可供使用的标准输入输出操作有如下几种：

  1. cin/cout
  2. cin/cout+取消同步
  3. scanf/printf
  4. 手写I/O优化

那么本文接下来将会对这几种方法进行简单的比较。

介绍

​ 首先对各种输入输出方式给出简单的介绍。

cin/cout

​ 这是C++标准库中提供的对读入输出流进行操作的对象，也是大部分C++程序所使用的读写方式。在流中需要开辟一个缓冲区，此处不过多赘述，但要知道的是这样的处理可以延长内存或者外部存储器的寿命，但这样也使得cin/cout的效率降低。

阅读全文
OIC++

队列

 发布于  收录于 OI

队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template<typename T,int maxnode>
struct QUE
{
	T ary[maxnode];
	int f,t;
	int cnt;
	QUE(){f=t=cnt=0;}
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	void push(const T& w)//if t+1!=f
	{
		ary[t++]=w;
		if(t==maxnode)t=0;
		++cnt;
	}
	T front(){return ary[f];}
	void pop()
	{
		++f;
		if(f==maxnode)f=0;
		--cnt;
	}
};
阅读全文
队列数据结构OIC++

Tarjan——强连通分量&最近公共祖先（LCA）

 发布于  收录于 OI

Tarjan——强连通分量&最近公共祖先（LCA）

  • 写在前面：这是我高二时给高一学弟学妹们唯二的讲课之一。时光荏苒，如今我早已AFO，将讲课内容整理如下，也为了纪念共同奋斗于OI的那些人，那些时光。
  • 写在前面的后面：时间仓促，不甚严谨，难免纰漏，敬请指正。
  • 写在前面的后面的后面：下文中的一些概念可能并没有严谨的依据，只是我为了方便理解构造的，还请谅解。

今天我们来讲讲Tarjan的两个算法：求最近公共祖先和强连通分量。

阅读全文
Tarjan栈强连通分量LCA并查集树图论OIC++

二分图匹配

 发布于  收录于 OI

二分图匹配

匈牙利最大匹配

邻接矩阵写法

例题：luogu3386

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

//luogu3386 二分图匹配 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=1003;

int n,m,e;
bool d[maxn][maxn];
void input()
{
	scanf("%d%d%d",&n,&m,&e);
	for(int i=1;i<=e;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(y<=m)
			d[x][y]=true;
	}
}
int match[maxn];
bool used[maxn];
bool findPath(int k)
{
	for(int i=1;i<=m;++i)
	{
		if(d[k][i]&&!used[i])
		{
			used[i]=true;
			if((!match[i])||findPath(match[i]))
			{
				match[i]=k;
				return true;
			}
		}
	}
	return false;
}
int ans=0;
void Edmonds()
{
	for(int i=1;i<=n;++i)
	{
		memset(used,0,sizeof(used));
		if(findPath(i))
			++ans;
	}
}
int main()
{
	freopen("luogu3386_1.in","r",stdin);
	//freopen("luogu3386.out","w",stdout);
	input();
	Edmonds();
	printf("%d\n",ans);
	return 0;
}

邻接链表写法

例题：poj1274

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

/*
	poj1274
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
template<typename T>
bool read(T& w)
{
	char r;
	for(r=getchar();(r<48||r>57)&&r!=-1;r=getchar());
	if(r==-1)return false;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	return true;
}
const int maxn=303;
const int maxm=303;
int n,m;
struct EDGE
{
	int to,nxt;
	void init(int too,int nxtt)
	{
		to=too,nxt=nxtt;
	}
}edge[maxn*maxm];
int ek=0;
int node[maxn];
inline void addEdge(int from,int too)
{
	edge[++ek].init(too,node[from]);
	node[from]=ek;
}

void input()
{
	memset(node+1,0,n*sizeof(int));
	ek=0;
	int s,x;
	for(int i=1;i<=n;++i)
	{
		read(s);
		for(int j=1;j<=s;++j)
		{
			read(x);
			addEdge(i,x);
		}
	}
}

int match[maxm];
bool used[maxm];
bool findPath(int k)
{
	for(int i=node[k];i;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(!used[v])
		{
			used[v]=true;
			if(match[v]==0||findPath(match[v]))//如果还未安排或者可以腾出 
			{
				match[v]=k;
				return true;
			}
		}
	}
	return false;
}
int ans=0;
void solve()
{
	memset(match+1,0,m*sizeof(int));
	ans=0;
	for(int i=1;i<=n;++i)
	{
		memset(used+1,0,m*sizeof(bool));
		if(findPath(i))++ans;
	}
}

int main()
{
	freopen("poj1274_1.in","r",stdin);
	//freopen("poj1274.out","w",stdout);
	while(read(n),read(m))
	{
		input();
		solve();
		printf("%d\n",ans);
	}
	return 0;
}

参考资料

阅读全文
二分图匹配二分图图论OIC++

单调队列

 发布于  收录于 OI

单调队列

（以单调递增队列为例）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

template<typename T,int maxnode,bool comp(const T&,const T&) >
struct upQUE
{
	T ary[maxnode+1];
	int f,t;
	int cnt=0;
	upQUE(){f=t=cnt=0;}
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	T front(){return ary[f];}
	T tail(){return t==0?ary[maxnode]:ary[t-1];}
	void push(const T& w)
	{
		while(t!=f&&comp(w,tail()))
		{
			--t;
			if(t==-1)t=maxnode;
		}
		ary[t++]=w;
		if(t==maxnode+1)t=0;
		++cnt;
	}

	void pop()
	{
		++f;
		if(f==maxnode+1)f=0;
		--cnt;
	}
};
阅读全文
单调队列队列单调性数据结构OIC++

堆

 发布于  收录于 OI

堆

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

//heap
template<typename T,bool comp(const T& a,const T& b)>
struct HEAP
{
	T ary[maxnode];
	int f;
	HEAP(){f=0;}
	bool empty(){return f==0;}
	void push(const T& w)
	{
		ary[++f]=w;
		for(int k=f;k!=1&&comp(ary[k],ary[k/2]);k/=2)
		{
			Swap(ary[k],ary[k/2]);
		}
	}
	T top(){return ary[1];}
	T pop()
	{
		T tmp=ary[1];
		ary[1]=ary[f--];
		for(int k=1,son=k*2;son<=f;k=son,son=k*2)
		{
			if(son+1<=f&&comp(ary[son+1],ary[son]))
				++son;
			if(comp(ary[son],ary[k]))
				Swap(ary[k],ary[son]);
			else break;
		}
		return tmp;
	}
};
阅读全文
堆二叉堆树数据结构OIC++

链表

 发布于  收录于 OI

链表

普通双向链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

//list
const int maxnode=10003;
template<typename T>
struct LIST
{
	int pre[maxnode],nxt[maxnode];
	T ary[maxnode];
	int f;
	int endd;
	LIST()
	{
		f=0;
		endd=maxnode-1;
		nxt[0]=endd;
	}
	void clear()
	{
		f=0;
		endd=maxnode-1;
		nxt[0]=endd;
	}
	void insert(int k,const T& w)//insert in front of k
	{
		ary[++f]=w;
		int pree=pre[k],nxtt=k;
		pre[nxtt]=nxt[pree]=f;
		nxt[f]=nxtt;
		pre[f]=pree;
	}
	void del(int k)
	{
		int pree=pre[k],nxtt=nxt[k];
		pre[nxtt]=pree;
		nxt[pree]=nxtt;
	}
	int begin()
	{
		return nxt[0];
	}
	int end()
	{
		return endd;
	}
};

支持内存回收的双向链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

template<typename T,int size>
struct QUE
{
	T ary[size];
	int f,t,cnt;
	QUE(){f=t=cnt=0;}
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	void push(const T& w)
	{
		ary[t++]=w;
		if(t==size)t=0;
		++cnt;
	}
	T top(){return ary[f];}
	void pop()
	{
		++f,--cnt;
		if(f==size)f=0;
	}
};
template<typename T,int size>
struct memLIST
{
	 T ary[size+1];
	 int pre[size+1],nxt[size+1];
	 int f;
	 QUE<int,size> mem;
	 int endd;
	 memLIST()
	 {
	 	memset(pre,0,sizeof(pre));
	 	memset(nxt,0,sizeof(nxt));
	 	f=0;
	 	mem.clear();
	 	nxt[0]=endd;
	 	endd=size;
	 }
	 void clear()
	 {
	 	memset(pre,0,sizeof(pre));
	 	memset(nxt,0,sizeof(nxt));
	 	f=0;
	 	mem.clear();
	 	nxt[0]=endd;
	 	endd=size;
	 }
	 T operator[](int k)
	 {
	 	return ary[k];
	 }
	 void del(int k)
	 {
	 	int pree=pre[k],nxtt=nxt[k];
	 	nxt[pree]=nxtt;
	 	pre[nxtt]=pree;
	 	pre[k]=nxt[k]=0;
	 	mem.push(k);
	 }
	 void insert(const T& w,int k)//insert in front of k
	 {
	 	int id;
	 	if(!mem.empty())
		 	id=mem.top(),mem.pop();
	 	else id=++f;
	 	int pree=pre[k],nxtt=k;
	 	pre[id]=pree;
	 	nxt[id]=nxtt;
	 	nxt[pree]=pre[nxtt]=id;
	 	ary[id]=w;
	 }
	 int begin()
	 {
	 	return nxt[0];
	 }
	 int end()
	 {
	 	return endd;
	 }
};
阅读全文
链表数据结构OIC++
0%