题目描述

/**
题目来源： Ural 1079
基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题 收藏  关注
有这样一个序列a：
a[0] = 0
a[1] = 1
a[2i] = a[i]
a[2i+1] = a[i] + a[i+1]

输入一个数N，求a[0] - a[n]中最大的数。
a[0] = 0, a[1] = 1, a[2] = 1, a[3] = 2, a[4] = 1, a[5] = 3, a[6] = 2, a[7] = 3, a[8] = 1, a[9] = 4, a[10] = 3。
例如：n = 5，最大值是3，n = 10，最大值是4。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10)
第2 - T + 1行：T个数，表示需要计算的n。（1 <= n <= 10^5)
Output
共T行，每行1个最大值。
Input示例
2
5
10
Output示例
3
4
/*

解题思想

/* 本题一看就明白那个求解规则，应为多组数组， 所以采用打表，然后直接查表即可。 */

代码

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //数据量
        int T = sc.nextInt();
        //init
        //存输入数据
        int[] a = new int[T];
        //记录输入数据的最大值
        int max = Integer.MIN_VALUE;
        //更新所求结果的最大值
        int max_two = Integer.MIN_VALUE;
        //INPUT
        for(int i=0; i<T; ++i){
            a[i] = sc.nextInt();
            max = Math.max(max, a[i]);
        }
        //init
        //get_max[i]表示数字i所求的结果最大值
        int[] get_max = new int[max+1];
        //dp[i]表示原题中的a[i]的值
        int[] dp = new int[max+1];
        if(max > 0){
           dp[0] = 0;
           get_max[0] = 0;
        }
        if(max > 1){
           dp[1] = 1;
           get_max[1] = 1;
        }
        for(int i=2; i<=max; ++i){
            if(i % 2 == 0){
                dp[i] = dp[i/2];
            }else{
                dp[i] = dp[(i-1)/2] + dp[(i+1)/2];
            }
            max_two = Math.max(max_two, dp[i]);
            get_max[i] = max_two;
        }
        for(int i=0; i<T; ++i){
            System.out.println(get_max[a[i]]);
        }
    }
}