[BZOJ 1996] [HNOI 2010] 合唱队

区间动态规划。

三维状态:f[i][j][k=0/1] 表示排出理想队形第 i~j 位,且最后排上去的一个当 k=0 时是 i,当 k=1 时为 j。

因为新的数只能加在当前已有区间的左右端点,故 f[i][j][k] 区间只能由 f[i+1][j][t] 与 f[i][j-1][t] 转移得到。具体来说,有如下转移:


1
2
3
4
f[i-1][j][0] += f[i][j][0] (a[i-1] < a[i])
f[i][j+1][1] += f[i][j][0] (a[j+1] > a[i])
f[i-1][j][0] += f[i][j][1] (a[i-1] < a[j])
f[i][j+1][1] += f[i][j][1] (a[j+1] > a[j])

初始化时把 f[i][i][0] 与 f[i][i][1] 其中一个设为 1,另一个设为 0。如果都设为 1,则会导致单个数有两种放置方式。

代码如下:

继续阅读[BZOJ 1996] [HNOI 2010] 合唱队