题目大意：给定一颗无穷大的完全二叉树，根节点的标号为$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了.

详情见代码.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
ll f[90][2];
ll fib[90];
int ins[90],cnt;
int main(){
	ll n;
	cin>>n;
	int i,j;
	for(fib[1]=1,fib[2]=2,i=3;i<=88;++i)
		fib[i]=fib[i-1]+fib[i-2];
	for(i=88;i>=1;--i)
		if(n>=fib[i])
			n-=fib[ins[++cnt]=i];
	f[cnt][1]=1;
	f[cnt][0]=(ins[cnt]-1)>>1;
	for(i=cnt-1;i>=1;--i){
		f[i][1]=f[i+1][0]+f[i+1][1];
		f[i][0]=f[i+1][0]*((ins[i]-ins[i+1])>>1)+f[i+1][1]*((ins[i]-ins[i+1]-1)>>1);
	}
	cout<<f[1][0]+f[1][1]<<endl;
	return 0;
}

思路:

首先将颜色分段.

令\(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的代码)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 510
int a[N],col[N],cnt[N],id;
 
int f[N][N];
int main(){
    int n;scanf("%d",&n);
    register int i,j,k,p;
    for(i=1;i<=n;++i)scanf("%d",&a[i]);
    for(i=1;i<=n;){
        col[++id]=a[i],cnt[id]=1;
        for(j=i;j!=n&&a[j]==a[j+1];++j,++cnt[id]);
        i=j+1;
    }
     
    for(k=1;k<=id;++k){
        for(i=1;i+k-1<=id;++i){
            j=i+k-1;
            if(i==j)f[i][j]=(cnt[i]>=3?1:(3-cnt[i]));
            else{
                f[i][j]=~0U>>1;
                for(p=i;p<j;++p)f[i][j]=min(f[i][p]+f[p+1][j],f[i][j]);
                if(k>=3&&col[i]==col[j])f[i][j]=min(f[i][j],f[i+1][j-1]+((cnt[i]+cnt[j]>=3)?0:(3-cnt[i]-cnt[j])));
            }
        }
    }
     
    printf("%d\n",f[1][id]);
    return 0;
}