【求解】A级问题 A025:动物身体状况管理

标签: 算法

前些天遇到一道算法问题,想了半天找不到最优解,希望各位高手提供答案。

问题

您是动物园管理员。我们正在为超重动物提供N天的饮食计划。

开始饮食前,动物体重为S毫克。
在第i天 (1 ≦ i ≦ N) 进行节食,动物的体重减轻了 Ai 毫克,但是如果他们什么都不做(不进行节食),它们就会变得懒惰,并且会增加 Bi 毫克的体重。

如果该动物体重超过T毫克,就会生病。因此,您应该制作动物的饮食计划,以使动物的体重在N天内的任何一天不超过T毫克。

在这一点上,您想知道每天可以用多少种方式分配“节食 或 不节食”,以便满足上述条件。让我们编写一个程序求解。

(例)

考虑示例1。目前,您正计划2天的饮食计划。开始时,动物体重为10毫克。
在此示例的情况下,有4种分配“节食或不节食”的方法,但是有3种分配方法,以使重量不超过20毫克。
因此,输出3。
在这里插入图片描述

输入值格式:

N S T
A_1 B_1
A_2 B_2
...
A_N B_N

・在第一行中,以整数N表示饮食天数,以整数S表示开始饮食前动物的体重,以整数T表示动物不应超过体重的上限,以空格分隔。
・在接下来的N行的第i行 (1 ≦ i ≦ N) 中,整数Ai表示在第i天进行节食时可能损失的体重,整数Bi代表不节食时增加的体重,以空格分隔。
・总输入为N + 1行。

期待的输出值:

请以整数形式输出每天分配“节食或不节食”的多少种方法,以便满足动物体重不超过T的条件。

条件:

所有测试用例均满足以下条件。
・1 ≦ N ≦ 35
・1 ≦ Ai, Bi ≦ 1,000,000,000 (1 ≦ i ≦ N)
・(所有的 A_i 的和) < S ≦ T ≦ 1,000,000,000

输入例1:

2 10 20
5 6
3 10

输出例1:

3

输入例2:

8 300 400
9 39
48 38
21 10
14 45
32 20
32 48
9 7
19 16

输出例2:

194

输入例3:

35 200 250
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5
5 5

输出例3:

32117925720

我写的程序

import java.io.InputStream;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
		execute(System.in);
    }

	private static void execute(InputStream in) {
		Scanner sc = new Scanner(in);
		String line = sc.nextLine();

		String[] ss = line.split(" ");
		int days = Integer.parseInt(ss[0]);
		int start = Integer.parseInt(ss[1]);
		int limit = Integer.parseInt(ss[2]);

		int[][] xs = new int[days][3];
		for (int i = 0; i < days; i++) {
			ss = sc.nextLine().split(" ");
			xs[i][0] = Integer.parseInt(ss[0]);
			xs[i][1] = Integer.parseInt(ss[1]);
		}

		xs[days - 1][2] = xs[days - 1][1]; 
		for (int i = days - 2; i >= 0; i--) {
			xs[i][2] = xs[i][1] + xs[i + 1][2];
		}

		long count = calc(xs, 0, start, limit);
		System.out.println(count);
		sc.close();
	}

	private static long calc(int[][] xs, int day, long start, long limit) {
		if (start > limit) {
			return 0;
		}

		if (day >= xs.length) {
			return 1;
		}

		long grows = xs[day][2];
		if (start + grows < limit) {
			return (long)Math.pow(2, xs.length - day);
		}

		long diet = start - xs[day][0];
		long grow = start + xs[day][1];

		day++;
		
		return calc(xs, day, diet, limit) + calc(xs, day, grow, limit);
	}

}

程序运行结果虽然正确,但是输入列3的程序运行时间耗时60秒左右。
最优解的程序,即使在最大天数(35天)的测试用例下,运行时间都应该小于5秒

版权声明:本文为yffrankwang原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yffrankwang/article/details/106423545