经典的3n+1,没有想到这道题调了一个晚上.
在Project Euler上看过这道题,于是按照那道题写了个部分DP.然后诡异的WA了.
调啊,调啊,只找到了一个trick:输入的两个数不一定小数在前大数在后.
然后呢,我这个程序是search,可加了一个预处理,for i=1~10000 do dp[i]=f(i),然后调用f(i)的地方改成dp[i],就过不了,都鬼了...怀疑数据范围有问题.

search可以1s过掉.

/*
  UVa 100; The 3n + 1 problem
  - sqybi's code
*/
//for my winsty

//#define DEBUG
#include
using namespace std;

const int nn = 1000001, mm = 10001;
int l, r, ll, rr, maxa;

int f(int i)
{
    if (i == 1)
        return 1;
    else if (i % 2)
        return f(i*3+1)+1;
    else
        return f(i/2)+1;
}

int main()
{
    #ifdef DEBUG
    freopen("uva100.in", "r", stdin);
    freopen("uva100.out", "w", stdout);
    #endif

    while (scanf("%d%d", &ll, &rr) != EOF)
    {
        l = ll;
        r = rr;
        if (l > r) swap(l, r);
        maxa = 0;
        for (int i = l; i <= r; ++ i)
            if (f(i) > maxa) maxa = f(i);
        printf("%d %d %d\n", ll, rr, maxa);
    }
}

You May Like These:

1. UVa 102 -- Ecological Bin Packing
2. DS大作业的两段代码
3. TopCoder SRM 413
4. NOIP 2008 第四题 双栈排序(twostack) 题解
5. 确定性有限状态自动机(DFA)