POJ 1207 笔记

初看觉得可能是数学题,仔细一想记忆化搜索就可以了。

笔记:

数据范太大,因此采用部分记忆化搜索。

注意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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>