bzoj 4069 [Apio2015]巴厘岛的雕塑

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4069

题解

设\(pre[i]\)表示前\(i\)个树的前缀和。

对于\(A > 1\)的数据:

从高到低枚举每一位,设\(f[i][j]\)表示前\(i\)个数分成\(j\)段,在答案中之前枚举过的位不改变的情况下,能否使当前位为\(0\);

状态转移方程:

\[f[i][j]|=f[k][j-1]\&chk(pre[i]-pre[k]),\quad 0\leq k < i\]

其中\(chk\)函数判断:\([k+1,i]\)的当前枚举到的这一位应为\(0\);若答案之前某位为\(1\),则\([k+1,i]\)区间的这一位可以为\(1\)或\(0\),否则该区间这一位必须为\(0\);

对于每一位,如果\(f[n][i],\quad A\leq i\leq B\)中有一个为\(1\),则答案这一位为\(1\);

对于其余数据:

从高到低枚举每一位,设\(g[i]\)表示前\(i\)个数最小能分成几段;

状态转移方程:

\[g[i]=min(g[i],g[j]+1),\quad 0\leq j < i,\quad chk(pre[i]-pre[j])==1\]

对于每一位,如果\(g[n]\leq B\),则答案这一位为\(1\)。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注