昨晚笔试没做出来,记一个大佬的思路。
输入:
4 //订单数量
1 2 3 5 //订单开始时间
3 4 6 8 //订单结束时间
210 190 200 300 //订单收益
输出:
510 //最大收益
import java.util.Scanner; public class test { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int orderCount = scanner.nextInt(); startTime = new int[orderCount]; endTime = new int[orderCount]; value = new int[orderCount]; for (int i = 0; i < orderCount; i++) { startTime[i] = scanner.nextInt(); } finishTime = 0; for (int i = 0; i < orderCount; i++) { endTime[i] = scanner.nextInt(); //finishTime = Math.max(finishTime, endTime[i]); } for (int i = 0; i < orderCount; i++) { value[i] = scanner.nextInt(); } maxValue = 0; dfs(0, 0); System.out.println(maxValue); } static int[] startTime; static int[] endTime; static int[] value; static int maxValue = 0; //static int finishTime = 0; static void dfs(int current, int sumValue) { //counter用来计数,还有能添加进来的订单counter就不为0 //如果为0,代表没有订单能添加进来了,将此时的总收益sumVaule和maxValue对比 int counter = 0; for(int i = 0; i < startTime.length; i++){ if(current <= startTime[i]){ dfs(endTime[i], sumValue + value[i]); counter ++; } } if(counter == 0){ maxValue = Math.max(maxValue, sumValue); } //一次dfs结束,返回到上一层的for循环里,寻找下一个符合条件的订单继续dfs } }