一、题目
1.原题
Wonderland是小王居住地一家很受欢迎的游乐园。
Wonderland目前有4种售票方式，
分别为一日票（1天）、三日票（3天）、周票（7天）和月票（30天）。
每种售票方式的价格将由一个数组给出，
每种票据在票面时限内可以无限制的进行游玩。
例如，小王在第10日买了一张三日票，小王可以在第10日、第11日和第12日进行无限制的游玩。
小王计划在接下来一年内多次游玩该游乐园。
小王计划的游玩日期将由一个数组给出。
现在，请您根据给出的售票价格数组和小王计划游玩日期数组，
返回完成游玩计划所需要的最低消费。
2.题目理解
售票方式：ticket:[1,3,7,30]
售票方式的价格：price:[88,258,588,1888]
(不考虑月份，0-365天）
游玩日期数组：plan[2，3，6，10，19，20，30，97]
二、思路与代码过程
1.思路
动态规划。
创建int[] dp = new int[366](从1开始），dp[i]表示到第i天一共花的金额。
eg：0，1天都不去，从第二天开始去，当前计费最小方式就是单日票dp[2]=88，如果选三日票dp[2]=258;第三天也去，dp[3]=dp[2]+88/258(dp[3-3]+258=0+258)选择小的那个，dp[3]=88*2;
当当前天数小于套餐天数时(6<7<30，按照dp[0]+price[2]/+price[3])。
2.代码过程
①main函数
public static void main(String[] args) {Scanner sc = new Scanner(System.in);int ticket[] = {1,3,7,30};System.out.println("请输入票价数组：");int price[] = new int[ticket.length];for (int i = 0; i < price.length; i++) {price[i] = sc.nextInt();}System.out.println("请输入游玩天数：");int days = sc.nextInt();System.out.println("请输入游玩日期数组：");int plan[] = new int[days];for (int i = 0; i < plan.length; i++) {plan[i] = sc.nextInt();}int expenditure = LowestCostCal(ticket,price,plan);System.out.println("完成该游玩计划需要的最低消费为："+expenditure);}②LowestCostCal
private static int LowestCostCal(int[] ticket, int[] price, int[] plan) {int dp[] = new int[366];boolean travel[] = new boolean[366];for (int day :plan){travel[day] = true;}for (int i = 1; i <= 365; i++) {if (!travel[i]) {dp[i] = dp[i-1];//不去游玩则与前天一致continue;}/*dp[Math.max(0,i-1)]+price[0]：表示第i天的消费=前一天i-1的消费dp[i-1]加上如果选择一日票的消费,其中Math.max(0,i-1)避免数组越界 */dp[i] = dp[i-1] + price[0];//单日票消费/*向前涵盖最小*/dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[0])]+price[0] );
//比较一日票dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[1])]+price[1] );
//比较三日票,dp[i]=今天单日票加之前价格和三天前价格加三天票价格之中较小的dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[2])]+price[2] );
//比较七日票dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[3])]+price[3] );
//比较月票}return dp[366];}三、运行结果
1.运行截图
2.完整代码
import java.util.Arrays;
import java.util.Scanner;public class test37 {public static void main(String[] args) {///*Scanner sc = new Scanner(System.in);int ticket[] = {1,3,7,30};System.out.println("请输入票价数组：");int price[] = new int[ticket.length];for (int i = 0; i < price.length; i++) {price[i] = sc.nextInt();}//System.out.println(Arrays.toString(price));System.out.println("请输入游玩天数：");int days = sc.nextInt();System.out.println("请输入游玩日期数组：");int plan[] = new int[days];for (int i = 0; i < plan.length; i++) {plan[i] = sc.nextInt();}//System.out.println(Arrays.toString(plan));//*///int ticket[] = {1,3,7,30};//int price[] = {88,258,588,1888};//int plan[] = {2,3,6,10,19,20,30,97};////int plan[] = {2,3,4,10,11,12,13,15,16,50,55,56,57,59,60,61,66,68};int expenditure = LowestCostCal(ticket,price,plan);System.out.println("完成该游玩计划需要的最低消费为："+expenditure);}private static int LowestCostCal(int[] ticket, int[] price, int[] plan) {int dp[] = new int[366];boolean travel[] = new boolean[366];for (int day :plan){travel[day] = true;}for (int i = 1; i <= 365; i++) {if (!travel[i]) {dp[i] = dp[i-1];//不去游玩则与前天一致continue;}/*dp[Math.max(0,i-1)]+price[0]：表示第i天的消费=前一天i-1的消费dp[i-1]加上如果选择一日票的消费,其中Math.max(0,i-1)避免数组越界 */dp[i] = dp[i-1] + price[0];//单日票消费/*向前涵盖最小*/dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[0])]+price[0] );//比较一日票dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[1])]+price[1] );//比较三日票,dp[i]=今天单日票加之前价格和三天前价格加三天票价格之中较小的dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[2])]+price[2] );//比较七日票dp[i] = Math.min(dp[i],dp[Math.max(0,i-ticket[3])]+price[3] );//比较月票}return dp[365];}
}
