Codeforces 567E Mausoleum

发表于 | 更新于 | 分类于 ， ， | 阅读次数：
本文字数： 3k | 阅读时长 ≈ 3 分钟

task

有n种底为1*1的长方体，高分别是1到n，而每种长方体只有两个。这种我们要求办这些长方体排成一排，满足前半部分单调不减，后半部分单调不增，两个部分也可以只有一个部分。如以下这些方案：
[1, 2, 2, 3, 4, 4, 3, 1];
[1, 1];
[2, 2, 1, 1];
[1, 2, 3, 3, 2, 1].
现在我们还有(1<=m<=100)个限制，如x>y,表示第x个长方体的高度大于第y个长方体的高度。这样的限制有5种，分别是”xy”,”x=y”,”x<=y”,”x>=y”。
求方案数。
$1<=n<=35$
$1<=m<=100$

solution

一看题目就知道是dp题。

$dp[L][R]$表示区间[L,R]内的方案数。

如果我们从小到大放每种的两个数我们可以知道我们只有三种放法：

  1. 两个数都放区间的左边。
  2. 两个数都放区间的右边。
  3. 一个数放区间的左边，一个数放区间的右边。

而且根据经验，这种状态的dp一般都是用记忆化搜索来写，所以我们状态的转移就是

而边界就是$R-L==1$.

但是这题并不是简单的记忆化搜索，而是还有限制条件的。

对于每个限制条件我们可以把这些数的关系存下来，然后每次转移前都判断一下。

对于所有情况，我们都需要判断一下放的这两个数的位置是否可以相等的关系。

  1. 两个数都放区间的左边，然后判断左边已经放的数中(即[1,L+2])是否有与在R位置上的数不满足小于关系的。接着是判断剩余没有放的数中(即[L+3,R])是否有与L和L+1位置上的数不满足大于关系的。
  2. 两个数都放区间的右边，然后判断左边已经放的数中(即[R-2,n])是否有与在L位置上的数不满足小于关系的。接着是判断剩余没有放的数中(即[L,R-3])是否有与R和R-1位置上的数不满足大于关系的。
  3. 一个数放区间的左边，一个数放区间的右边。那么我们就只用判断只剩余还没有放的数中是否有与L和R上的数不满足大于关系的。

Code

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 80
#define ll long long
using namespace std;
int n,rel[M][M];
ll dp[M][M];
int rep(char c){
	if(c=='<')return 1;
	if(c=='>')return 2;
	return 3;
}
void Init(char str[]){
	int len=strlen(str),a,b=0,c,t=1;
	for(int i=0;i<len;i++){
		if(str[i]==' '){
			if(t==1)a=b;
			if(t==2)
				if(b>10)c=(b==13)?4:5;
				else c=b;
			t++;b=0;
		}else if(str[i]<='9'&&str[i]>='0')b=b*10+str[i]-'0';
		else b=b*10+rep(str[i]);
	}
	if(a>b){
		swap(a,b);
		if(c<3)c=(c==1)?2:1;
		if(c>3)c=(c==4)?5:4;
	}
	rel[a][b]=c;
}
bool check1(int L,int R){
	if(rel[R][R+1]&&rel[R][R+1]<3)return 0;
	for(int i=R+1;i<=n;i++)
		if(rel[L][i]==1||rel[L][i]==3||rel[L][i]==4)return 0;
	for(int i=L;i<R;i++){
		if(rel[i][R]==1||rel[i][R+1]==1)return 0;
		if(rel[i][R]==3||rel[i][R+1]==3)return 0;
		if(rel[i][R]==4||rel[i][R+1]==4)return 0;
	}
	return !rel[L][R]||rel[L][R]==2||rel[L][R]==5;
}
bool check2(int L,int R){
	if(rel[L-1][L]&&rel[L-1][L]<3)return 0;
	for(int i=1;i<L;i++)
		if(rel[i][R]==2||rel[i][R]==3||rel[i][R]==5)return 0;
	for(int i=L+1;i<=R;i++){
		if(rel[L][i]==2||rel[L-1][i]==2)return 0;
		if(rel[L][i]==3||rel[L-1][i]==3)return 0;
		if(rel[L][i]==5||rel[L-1][i]==5)return 0;
	}
	return !rel[L][R]||rel[L][R]==1||rel[L][R]==4;
}
bool check3(int L,int R){
	for(int i=L+1;i<R;i++){
		if(rel[L][i]==2||rel[i][R]==1)return 0;
		if(rel[L][i]==3||rel[i][R]==3)return 0;
		if(rel[L][i]==5||rel[i][R]==4)return 0;
	}
	return !rel[L][R]||rel[L][R]>2;
}
ll dfs(int L,int R){
	if(R<=L)return 0;
	if(R-L==1)return rel[L][R]==0||rel[L][R]>2;
	ll &t=dp[L][R];
	if(t==-1){
		t=0;
		if(check1(L,R-1))t+=dfs(L,R-2);
		if(check2(L+1,R))t+=dfs(L+2,R);
		if(check3(L,R))t+=dfs(L+1,R-1);
	}
	return t;
} 
int main(){
	memset(dp,-1,sizeof(dp));
	int m,i,a,b;
	char str[10];
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=m;i++){
		gets(str);
		Init(str);
	}n*=2;
	cout<<dfs(1,n)<<endl;
	return 0;
}