今年的世界杯要开始啦,牛牛作为一个球迷,当然不会放过去开幕式现场的机会。但是牛牛一个人去又觉得太过寂寞,便想叫上了他的n个小伙伴陪他一起去莫斯科(一共n+1人)。当牛牛开始订开幕式的门票时,发现门票有m种套餐,每种套餐需要花费x元,包含y张门票,每张门票也可以单独购买,此时这张门票的价格为k元。请问牛牛要怎样选择购买门票,使得他花费的钱最少。(每种套餐可以购买次数没有限制)。
第一行输入三个数字n(0≤n≤999)、m(1≤m≤1000)和k(1≤k≤100000)
接下来m行,每行输入两个数字xi(1≤xi≤100000)和yi(2≤yi≤1000), 表示套餐的价格和套餐内包含的门票数量。
输出牛牛至少要花费的钱的数量。
2 2 5 6 2 13 3
11
//基本思路:刚开始不整理,就是将买几张票的钱数先存在dp中,等套餐,单买的情况都存好后, //整理dp[],整理的话有两种情况:①当前的票数要花的最少的钱数等于小于当前票数的最小钱的情况 //之和(因为小于当前票数的最少的钱已经整理好),②等于大于当前票数花的钱和当前的最小数 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int ticket[]=new int[1001];//表示买i张票所需要的最少的钱 int m=sc.nextInt(); int k=sc.nextInt(); for(int i=0;i<1001;i++){ ticket[i]=i*k; } for(int i=0;i<m;i++){ int mm=sc.nextInt(); int t=sc.nextInt(); ticket[t]=Math.min(ticket[t],mm); } for(int i=1;i<=n+1;i++){ int min=ticket[i]; for(int j=1;j<=1000;j++){ if(j<i) min=Math.min(min,ticket[j]+ticket[i-j]); else min=Math.min(min,ticket[j]); } ticket[i]=min; } System.out.println(ticket[n+1]); } }
public class Main { // 动态规划:dp[i]表示i个人的最小花销 public static void main(String[] args) { java.util.Scanner sc = new java.util.Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(), i, j; int price, num, dp[] = new int[n+2];// dp[0] == 0 for (i = 1; i < n+2; ++i) dp[i] = k * i; for (i = 0; i < m; ++i) { price = sc.nextInt(); num = sc.nextInt(); for (j = 1; j < n+2; ++j) dp[j] = Math.min(dp[j], dp[Math.max(0, j-num)] + price); } System.out.println(dp[n+1]); } }