题目传送锚点
在博客园食用更佳
题意比较明确，这里不再赘述。
::::info[思路]{open}
时限和 \(1 \le n \le 5 \times 10^6\) 告诉我们，这道题是个 dp。
定义 \(f_i\) 表示走到第 \(i\) 格需要的最短时间，最后输出 \(f_n\) 即可。
转移有两种（如题），第二种（战术换位）需要处理出 \(a_i\) 上一次出现的位置，比较好处理，具体的见代码中的 \(last\) 数组。
第一种也比较简单，处理完第 \(i\) 次战术换位后往后拓展即可，注意不要越界。
注意到题面说过：
请注意常数因子对程序效率的影响。
而处理分数是会用到 \(gcd\)，常数较大，所以应减少使用限制，比如我在代码第 \(51\) 行加了限制。这导致我在考场上卡常卡了半个小时，唐完了。
::::
::::success[代码]
#include<bits/stdc++.h>
#define int long long
using namespace std;int n,x,y,k,w,z[100],a[5000001],last[5000001];struct node
{int x;int y;
}s,f[5000001];node minn(node q,node p)
{x=q.x*p.y;y=p.x*q.y;if(x<=y) return q;return p;
}node add(node q,int xx,int yy)
{s.y=q.y*yy;s.x=q.x*yy+xx*q.y;return s;
}signed main()
{ios::sync_with_stdio(false);cin.tie();cout.tie();cin>>n;for(int i=1;i<=n;++i){cin>>a[i];f[i].x=0x7fffffff;f[i].y=1;last[i]=z[a[i]];z[a[i]]=i;}f[1].x=0;for(int i=1;i<=n;++i){if(last[i]!=0){s.x=f[last[i]].x+f[last[i]].y;s.y=f[last[i]].y;f[i]=minn(f[i],s);}if(f[i].x>100000000||f[i].y>100000000){k=__gcd(f[i].x,f[i].y);f[i].x/=k;f[i].y/=k;}w=min(n,i+a[i]);for(int j=i+1;j<=w;++j) f[j]=minn(f[j],add(f[i],j-i,a[i]));}k=__gcd(f[n].x,f[n].y);f[n].x/=k;f[n].y/=k;printf("%lld %lld",f[n].x,f[n].y);return 0;
}
::::