题目大意：给定一颗无穷大的完全二叉树，根节点的标号为$1$，对于每个节点若其标号为$x$，则其左儿子标号为$2x$，右儿子标号为$2x+1$。同时再给定$S$，求树上有多少条路径使得路径上节点的标号和恰为$S$。数据范围$S\leq{10^{15}}$。

题解:

首先我们用Fib贪心的找出一组解.

假如我们利用二进制存储得到的那组解.

例如15=13+2

就是(从小到大)010001,分别代表1,2,3,5,8,13.

由于我们知道由于Fib数列的性质,001等价于110.

所以我们需要知道找到的那组解一共能够变换出多少方案.

我们依次考虑得到的那组解中的每个1,令$f[i][0]$表示第$i$个一在变换后的方案中是$0$的方案数,$f[i][1]$同理.

我们首先观察001变换出110的性质,我们不难发现只能变换出这样的形式:

1->110->11010

即如果有$k$个空位,则有$\lfloor\frac{k}{2}\rfloor$种方案,知道了这些就不难dp了.

详情见代码.

代码:

思路:

首先将颜色分段.

令$f[i][j]$表示第$i$段到第$j$段全部清除最小的代价.

转移一:

$$f[i][j]=\min_{k=i}^{j-1}f[i][k]+f[k+1][j]$$

转移二:

$i=j$,直接转移

转移三:

$col[i]=col[j]$,$f[i][j]=f[i+1][j-1]+blabla...$

可是这样是不一定对的.

(做到这里在OJ上就可以AC了.)

他不能处理三个离散的珠子合并的情况.

比如1 2 2 1 3 3 1.

正确答案应该是2.

我们加一步判断,如果区间两端都是只有一个的话,尝试在区间中寻找同样颜色的,然后合并.

由于数据问题,这样判断是会WA的.但是这应该是正确答案.

(在OJ上可以AC的代码)