CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

==== 题面描述 ====
一个长度为 $n$ 的数列 $c$ ，对其赋值为 $0/1$ ，要求 $c_i$ 和 $c_{i+1},c_{i+k}$ 均不能同时为 $1$ 。求所有合法赋值情况下，赋值为 $1$ 的位置的 $w$ 的乘积的和。

$k \le n \le 300$

==== 题解 ====
考虑将序列每行 $k$ 个来变成一个不完整的矩形。这时候我们有两种算法：

第一种：我们考虑直接来轮廓线DP，这样的复杂度是 $O(有效状态数*n)$的。

第二种：我们考虑将其转置一下后再轮廓线DP，但是这时候还需要判断第一行和最后一行之间的合法性，所以复杂度是 $O(有效状态^2*n)$ 的。

这里的有效状态数都是斐波那契级别的，可以近似算作 $O(1.618^{len})$，那么第一种的复杂度就是 $O(1.618^k*n)$ ，第二种就是 $O(1.618^{2n/k}*n)$ 。平衡一下复杂度，考虑按照 $2*sqrt{n}$ 为阈值来分开做，算完时间复杂度是正好够的。

后记：我用那个GNU C++17是会超时的，但是换成GNU C++20那个就很轻松的过了（雾）。

CVBB ACM Team

用户工具

站点工具

页面工具