Pilot's Blog
0%

蓝桥oj1461最少砝码

发表于 分类于 ， ， Valine：
本文字数： 785 阅读时长 ≈ 1 分钟

题目

分析

贪心+动归

  • 当有1个砝码

  1. 可以称出的最大质量为1

  2. 称不出的最小质量为2

  • 当有2个砝码

  1. 要想得到在1个砝码时称不出来的质量2，新的砝码质量可以是1、2、3，但是4不行，因为4-1 = 3 > 2

  2. 由贪心的思想，要想得到最大质量区间，新砝码取3。原因如下图

  • 当有3个砝码

    1. 有2个砝码时得不到的最小质量是5
    2. 要想得到质量区间最大，新砝码要在尽可能大的前提下满足减去前2个砝码的和后依然能得到5。所以新砝码的最大质量为5(2个砝码时最小得不到得到质量) + 4(2个砝码时能得到的最大质量) = 9

  • 贪心

    1. dp[ i ]：在有i个砝码时能得到的最大质量

    2. 转移方程：

      1
      2
      3
      dp[i + 1] = dp[i] + maxFama 
      maxFama = dp[i] + (dp[i] + 1)
      dp[i + 1] = 3 * dp[i] + 1

估计开多大空间

讲解视频

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;

public class Main {
	static int maxNum = (int)(10e6);
	static int[] dp = new int[maxNum];
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int target = scan.nextInt();
		dp[1] = 1;
		int count = 1;
		int minBoundry = 2;
		while(minBoundry < target) {
			int maxFama = minBoundry + dp[count];
			minBoundry = dp[count] + maxFama + 1;
			dp[++count] = minBoundry - 1;
		}
		System.out.println(count);
		scan.close();
	}
}