【IOI2016】按数目填色

题意:给定\(n\)个格子,每个格子需要被染上黑色或者白色,某些格子被钦定了颜色,并且按顺序给出所有的极大连续黑段的长度,问每个格子可能是哪些颜色。保证至少存在一组合法解。

 

令\(a_{i,j,k}\)表示第\(i\)格从左到右已经选择了\(j\)个格子,当前格子是白色/黑段的末尾是否可行。

令\(b_{i,j,k}\)表示第\(i\)格从右到左还需要选择\(j\)个格子,当前格子是白色/黑段的末尾是否可行。

直接dp即可求出。

那么一个格子\(i\)可以为白色当且仅当存在\(j\)使得\(a_{i,j,0}=b_{i,j,0}=1\)。

若一个格子\(i\)满足存在\(j\)使得\(a_{i,j,1}=b_{i+1,j,0}=1\)那么从\(i\)向前第\(j\)个黑段的长度的格子都可以为黑色。用一个指针记录最远位置即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz