OI题解 - A decorative fence[POJ 1037]

这也算是我在hexo博客上面写的第一篇博客~
开始研究一些“有后效性的”DP


『题目』

(自己大概翻译了一下) 有n个木板,木板的高度为1~n的排列,你需要把它们排成“漂亮的栅栏”,即满足

(也就是一高一低)。
将所有方案按木板排列高度的字典序排列,求出第C个方案(保证存在)。
$0 < N\leq 20, C > 0$
T组数据($T\leq 100$)。


『解析』

这道题有一个重要的性质——栅栏的高度具体是多少对能否构成方案并不重要,起主要影响的是它们的相对高度。又因为高度是一个排列(没有重复),所以我们只要知道有多少个木板,我们就可以获得它们的相对高度!

而两种漂亮的栅栏我们可以把它抽象成:①”M”型,第一个栅栏比第二个栅栏矮;②”W”型,第一个栅栏比第二个栅栏高;

根据这两点,可以写出状态定义:

$dp[i][j][0/1]表示将 表示将 i$ 个木板排成一个漂亮的栅栏,且开头是其中第 j 高的木板的 W型/M型 方案总数。

状态转移方程式则是:

我们将第 $j$ 高的栅栏放在第一个,那么剩下 $i-1$ 个栅栏,因为第 $j$ 个栅栏被拿走,所以 $j$ 之后的所有栅栏都会往前挪一位,形成新的相对高度关系。此时若要构成W型,就要在新的相对高度中选择第 1~j-1 高的栅栏,若要构成M型,就要在新的高度中选择第 j~i-1 高的栅栏(新的相对高度的第 $j$ 高相当于原来相对高度关系的第 $j+1$ 高)。

上面是初始化。接下来我们需要确定方案——逐位确定。先枚举 $i$,表示现在正在求方案中第 i 个栅栏的高度,然后从小到大(因为字典序)枚举高度 $j$ ,如果 $j$ 还没有用过,尝试放入 $j$:

设求得的方案为 ans[];j 在还没有用过的栅栏中是第 k 高;

当 i=1 时,则可能是 W型也可能是 M型,所以方案数为 $dp[n][j][0]+dp[n][j][1]$;

当 i=2 时,则 j 的选择就确定了 M型或W型,所以判断 j 和 ans[1] 的大小关系,如果 j > ans[1] 则为W型,方案数为 dp[n-1][j][0];

当 $i > 2$ 时,M型或W型就确定了,所以我们根据 $ans[i-2]$ 和 $ans[i-1]$ 的大小关系就可以确定 $j$ 和 $ans[i-1]$ 的大小关系,要么是 $ans[i-2] < ans[i-1] > j$(M型) 要么是 $ans[i-2] > ans[i-1] < j$(N型)。当 $j$ 满足上述条件时,根据 M或N 型,它对应的方案数为 $dp[n-i+1][k][0/1]$;

如果 j 可以放入(也就是满足上面的条件),那么我们统计一下方案总数为 $tmp$,如果 $tmp\leq C$,那么 j 就是第 i 位的答案。

一直这样计算直到确定完所有位为止~具体见代码。


『源代码』

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=20;
ll dp[N+7][N+7][2];
ll C;
int ans[N+7];
bool vis[N+7];
int n;
int main(){
int T;scanf("%d",&T);
dp[1][1][0]=dp[1][1][1]=1;
for(int i=2;i<=N;i++)
for(int j=1;j<=i;j++){
//W
for(int k=1;k<j;k++)
dp[i][j][0]+=dp[i-1][k][1];
//M
for(int k=j;k<i;k++)
dp[i][j][1]+=dp[i-1][k][0];
}
while(T--){
scanf("%d%lld",&n,&C);
for(int i=1;i<=n;i++){ //确定第i位
for(int j=1,k=0;j<=n;j++){ //假设第i位放j
ll tmp=C; //方案数还剩下多少(这里不太一样,因为我写的时候是将C减去当前方案数……)
if(!vis[j]){ //不能重复使用
k++; //j是没有使用过的数中第k大
if(i==1) tmp-=dp[n][k][0]+dp[n][k][1]; //M或N不确定
else if(j<ans[i-1] && (i==2 || ans[i-2]<ans[i-1])) tmp-=dp[n-i+1][k][1]; //M
else if(j>ans[i-1] && (i==2 || ans[i-2]>ans[i-1])) tmp-=dp[n-i+1][k][0]; //W
if(tmp<=0){ //也就相当于方案总数>=C
vis[j]=true;ans[i]=j; //把j确定为第i位
break;
}
}
C=tmp; //更新剩余的需确定的方案数
}
}
for(int i=1;i<=n;i++){
i==n? printf("%d\n",ans[i]):printf("%d ",ans[i]);
vis[i]=false;ans[i]=0;
}
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问

0%