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种，分别是”x<y”,”x>y”,”x=y”,”x<=y”,”x>=y”。
求方案数。
$1<=n<=35$
$1<=m<=100$
solution
一看题目就知道是dp题。
$dp[L][R]$表示区间[L,R]内的方案数。
如果我们从小到大放每种的两个数我们可以知道我们只有三种放法：
- 两个数都放区间的左边。
- 两个数都放区间的右边。
- 一个数放区间的左边，一个数放区间的右边。
而且根据经验，这种状态的dp一般都是用记忆化搜索来写，所以我们状态的转移就是
$$dp[L][R]=dp[L+2][R]+dp[L][R−2]+dp[L+1][R−1]$$
而边界就是$R-L==1$.
但是这题并不是简单的记忆化搜索，而是还有限制条件的。
对于每个限制条件我们可以把这些数的关系存下来，然后每次转移前都判断一下。
对于所有情况，我们都需要判断一下放的这两个数的位置是否可以相等的关系。
- 两个数都放区间的左边，然后判断左边已经放的数中(即[1,L+2])是否有与在R位置上的数不满足小于关系的。接着是判断剩余没有放的数中(即[L+3,R])是否有与L和L+1位置上的数不满足大于关系的。
- 两个数都放区间的右边，然后判断左边已经放的数中(即[R-2,n])是否有与在L位置上的数不满足小于关系的。接着是判断剩余没有放的数中(即[L,R-3])是否有与R和R-1位置上的数不满足大于关系的。
- 一个数放区间的左边，一个数放区间的右边。那么我们就只用判断只剩余还没有放的数中是否有与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;
}
|