初看觉得可能是数学题,仔细一想记忆化搜索就可以了。
笔记:
数据范太大,因此采用部分记忆化搜索。
注意ACM常见坑,给定区间i , j时并未保证i <= j
另外注意输出要求维持原i, j顺序,不能直接swap原变量。
# include <cstdio>
int r[100007] = {0};
int dfs(int x)
{
if ( x < 100007 && r[x] ) return r[x];
int res;
if ( x&1 ) res = dfs((x<<1)+x+1) + 1;
else res = dfs(x>>1) + 1;
if ( x < 100007 ) r[x] = res;
return res;
}
int main()
{
int i, j, a, b, k, m;
r[1] = 1;
while( scanf("%d%d", &i, &j) != EOF )
{
if ( j < i ) a = j, b = i;
else a = i, b = j;
m = 0;
for (k = a; k <= b; ++k ) if ( dfs(k) > m ) m = dfs(k);
printf("%d %d %d\n", i, j, m);
}
return 0;
}