长话短说
前面不说了，后半部分就是问你一个方案数，最少用几个平台可以造出
随便试一个
当为
到每个平台的方案数为
1 2 3 4 5 6 7 8 9 10 11 12 13 14(n+1)
1 1 0 1 1 1 0 0 1 1 1 1 0
1 1 2 3 3 6 9 15 15 15 30 45 75 120分开来看，抛去第一个，然后错一位，以每个
1 1 0
1 2 3
1 1 1 0 0
3 6 9 15 15
1 1 1 1 0
15 30 45 75 120我们发现
1.好像斐波那契数列——实际上就是
2.多个
所以我们可以用
而每一部分的最后一个又会成为下一个的第一个
所以成了若干个斐波那契数相乘的形式
显然，答案为这若干个斐波那契数的在斐波那契数列中的位置（也就是
更显然，尽量选择较大的因数是更优的
所以我们用正确的贪心，写出了错误的代码
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1e6+10;
int T,n,f[MAXN],fib[MAXN];
int main()
{
scanf("%d",&T);
fib[1]=1,fib[2]=2;
for(int i=3;fib[i-1]<=1e6;i++) fib[i]=fib[i-1]+fib[i-2];
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n+1;i++) f[i]=0;
f[1]=1;
for(int i=1,a;i<=n;i++)
{
scanf("%d",&a);
if(a) f[i+2]+=f[i];
f[i+1]+=f[i];
}
printf("%d ",f[n+1]);
int tmp=f[n+1],ans=0;
for(int i=30;i>=2;i--) while(tmp%fib[i]==0) ans+=i,tmp/=fib[i];
(f[n+1]==1)?puts("1"):printf("%d\n",ans);
}
return 0;
}为什么，因为我们在分解因数的时候不能像分解质因数一样，因为有可能你分解出来了这个因数，然后就不能继续分解成斐波那契数相乘的形式了，所以我们要
bool Check(int x)
{
if(x==1) return true;
for(int i=30;i>=2;i--) if(x%fib[i]==0&&Check(x/fib[i])) return true;
return false;
}跑得很快，要比题解的代码快不少
对了，还要特判
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=1e6+10;
int T,n,f[MAXN],fib[MAXN];
bool Check(int x)
{
if(x==1) return true;
for(int i=30;i>=2;i--) if(x%fib[i]==0&&Check(x/fib[i])) return true;
return false;
}
int main()
{
scanf("%d",&T);
fib[1]=1,fib[2]=2;
for(int i=3;fib[i-1]<=1e6;i++) fib[i]=fib[i-1]+fib[i-2];
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n+1;i++) f[i]=0;
f[1]=1;
for(int i=1,a;i<=n;i++)
{
scanf("%d",&a);
if(a) f[i+2]+=f[i];
f[i+1]+=f[i];
}
printf("%d ",f[n+1]);
int tmp=f[n+1],ans=0;
for(int i=30;i>=2;i--) while(tmp%fib[i]==0&&Check(tmp/fib[i])) ans+=i,tmp/=fib[i];
(f[n+1]==1)?puts("1"):printf("%d\n",ans);
}
return 0;
}