-2

3n+1 问题

时间限制：2000/1000 MS（Java/其他）内存限制：65536/32768 K（Java/其他）提交总数：18416 接受提交：6803

问题描述 计算机科学中的问题通常被归类为属于某一类问题（例如，NP、不可解、递归）。在这个问题中，您将分析一个算法的属性，该算法的分类对于所有可能的输入都是未知的。

考虑以下算法：

1.      input n

2.      print n

3.      if n = 1 then STOP

4.           if n is odd then n <- 3n + 1

5.           else n <- n / 2

6.      GOTO 2

给定输入 22，将打印以下数字序列 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

据推测，对于任何整数输入值，上述算法将终止（当打印 1 时）。尽管算法很简单，但这个猜想是否正确尚不清楚。然而，已经验证了对于所有整数 n，使得 0 < n < 1,000,000（事实上，对于比这更多的数字。）

给定输入 n，可以确定打印的数字数量（包括 1）。对于给定的 n，这称为 n 的周期长度。在上面的例子中，循环长度 22 是 16。

对于任何两个数字 i 和 j，你要确定 i 和 j 之间所有数字的最大循环长度。

输入 输入将由一系列整数对 i 和 j 组成，每行一对整数。所有整数都将小于 1,000,000 且大于 0。

您应该处理所有整数对，并为每对确定 i 和 j 之间（包括 i 和 j）之间所有整数的最大循环长度。

您可以假设没有任何操作会溢出 32 位整数。

输出 对于每对输入整数 i 和 j，您应该输出 i、j 以及介于 i 和 j 之间且包括 i 和 j 的整数的最大循环长度。这三个数字应至少用一个空格隔开，所有三个数字都在一行，每行输入对应一行输出。整数 i 和 j 必须按照它们在输入中出现的顺序出现在输出中，并且后面应该是最大循环长度（在同一行上）。

样本输入 1 10 100 200 201 210 900 1000

样本输出 1 10 20 100 200 125 201 210 89 900 1000 174

4

1 回答 1

0

如果您使用普通方式。对于每种情况，请计算所有整数的解决方案。因此，您可以为 1 到 1,000,000 之间的所有人计算解决方案，而不是存储在数组中。使用 ST 方式计算一个新的 dp[N][M]。比有查询时，你可以得到 O(1) 次的 ans；或者您可以使用 Segment Tree 来获取答案。但我不确定它不会得到 TLE ......

for(int j=0;j<=log(N);j++)
    for(int i=1;i<=N;i++)
        dp[i][j]=max(dp[i][j-1]+dp[i+pow(2,j-1)][j-1];
于 2013-10-22T09:19:36.640 回答