P3146 [USACO16OPEN]248 题解
Doveqise
2019-04-06 09:59:18
这道题,一道简单区间DP,在这里主要介绍一下加强版[P3147 [USACO16OPEN]262144](https://www.luogu.org/problemnew/show/P3147)别人不太注意的数据范围问题...(假双倍经验)
我们注意到题中说2≤N≤262 144,那么这个262 144是多少呢?
266 144=$2^{18}$,所以我们循环时就循环到40+18=58就好。
细节见代码↓(不想用58系列)
```c++
#include<bits/stdc++.h>
using namespace std;
int f[60][262144+5],ans;
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){int t;scanf("%d",&t);f[t][i]=i+1;}
for(int i=2;i<=60;i++) for(int j=1;j<=n;j++){
if(!f[i][j]) f[i][j]=f[i-1][f[i-1][j]];
if(f[i][j]) ans=i;}
printf("%d\n",ans);
return 0;
}
```