洞天
题目背景
留云借风真君讲起了申鹤小时候的故事。
题目描述
为了供徒弟修炼，留云借风真君建造了一个洞天。从洞天的入口进入，眼前共有 $n+1$ 个平台排列成一线，依次编号为 $1$ 到 $n+1$，其中 $n+1$ 号平台是终点。留云借风真君在一些平台上制造了风场，为了保证安全，她不能在 $n$ 号平台制造风场。每次修炼时，申鹤初始在 $1$ 号平台。如果当前脚下的平台没有风场，那么她只能跳到下一个平台；如果当前脚下的平台有风场，那么她可以选择跳到下一个平台或者是下下个平台。到达 $n+1$ 号平台视为修炼完成。
留云借风真君虽然很会聊天，但是数学不好，现在她给你一个洞天，请你帮她计算申鹤有多少种不同的方案来完成修炼，两种方案视为不同当且仅当存在某一个平台在一种方案中停留过而另一种方案不曾停留。
留云借风真君虽然很爱发明，但是手头很紧，她希望你告诉她，在满足完成修炼的方案数不变的前提下，除终点外最少可以用几个平台来构造洞天（风场可以重新设置，风场数量没有限制）。
输入格式
共有 $T$ 组询问。
第一行一个正整数 $T$ 表示询问的组数。
接下来对于每组询问：
第一行一个正整数 $n$，表示除终点外平台的数量。
第二行 $n$ 个只为 $0$ 或 $1$ 的整数 $a_i$，$a_i=0$ 表示 $i$ 号平台上没有风场，$a_i=1$ 表示 $i$ 号平台上有风场。
输出格式
共 $T$ 行，每行两个用空格隔开的正整数，第一个正整数表示申鹤在该洞天完成修炼的不同方案数，第二个正整数表示在满足完成修炼的方案数不变的前提下，最少可以用几个平台（不算终点）来构造洞天。
样例 #1
样例输入 #1
3
8
0 0 1 0 1 1 1 0
6
0 1 1 0 1 0
2
1 0样例输出 #1
10 6
6 5
2 2提示
样例解释
对于第一组数据，共有 $10$ 种方案通过洞天。
1->2->3->4->5->6->7->8->9
1->2->3->4->5->6->7->9
1->2->3->4->5->6->8->9
1->2->3->4->5->7->8->9
1->2->3->4->5->7->9
1->2->3->5->6->7->8->9
1->2->3->5->6->7->9
1->2->3->5->6->8->9
1->2->3->5->7->8->9
1->2->3->5->7->9洞天的构造方案为 1 0 1 1 1 0，共使用 $6$ 个平台。
对于第二组数据，共有 $6$ 种方案通过洞天。
1->2->3->4->5->6->7
1->2->3->4->5->7
1->2->3->5->6->7
1->2->3->5->7
1->2->4->5->6->7
1->2->4->5->7洞天的构造方案为 1 1 0 1 0，共使用 $5$ 个平台。
对于第三组数据，共有 $2$ 种方案通过洞天。
1->2->3
1->3洞天的构造方案为 1 0，共使用 $2$ 个平台。
数据范围
对于所有数据，$1\leq n\leq 10^6$，$1\leq T\leq 10^6$，保证所有 $n$ 的和不超过 $10^6$，对于每组询问，保证完成修炼的不同方案数不超过 $10^6$。
Subtask #1（30 points）：$1\leq T\leq 10$，$1\leq n\leq 16$，且保证每个给定的洞天都已经用了尽可能少的平台。
Subtask #2（30 points）：保证每个给定的洞天都已经用了尽可能少的平台。
Subtask #3（20 points）：$1\leq T\leq 10$。
Subtask #4（20 points）：无特殊限制。
Solution
动态规划、斐波那契数列
使用 $f_i$ 表示 $f_0=1,f_1=1$ 的斐波那契数列第 $i$ 项，通过 $n$ 个平台构成的连续段（$n-1$ 个风场后接 $1$ 个普通平台）的方案数即为 $f_n$。通过每一段的方案数相乘可以得到总方案数。
题目保证通过洞天的方案数不超过 $10^6$，打表发现 $f_{30}>10^6$，所以洞天中任意连续段的平台数不超过 $29$。动态规划，设计 $dp_i$ 为构造通过方案数为 $i$ 的洞天需要的最小平台数量，枚举连续段平台数量转移得到答案。
#include<bits/stdc++.h>
using namespace std;
constexpr int lim=1'000'000;
int n,sum,ans,f[35],dp[1'000'005];
void solution(){
cin>>n,ans=1,sum=1;
for(int i=1;i<=n;i++){
static int x;
cin>>x,sum+=x;
if(!x) ans*=f[sum],sum=1;
}
cout<<ans<<' '<<dp[ans]<<'\n';
}
int T;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
memset(dp,63,sizeof(dp));
cin>>T,f[0]=1,f[1]=1;
for(int i=2;i<=30;i++) f[i]=f[i-2]+f[i-1];
for(int i=1;i<=30;i++) if(f[i]<=lim) dp[f[i]]=i;
for(int i=1;i<=lim;i++) if(dp[i]<=lim)
for(int j=2;j<=30;j++) if(1ll*i*f[j]<=lim)
dp[i*f[j]]=min(dp[i*f[j]],dp[i]+j);
while(T--) solution();
return 0;
}