首页 > 试题广场 >

牛牛与世界杯门票

[编程题]牛牛与世界杯门票

热度指数：1214 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

今年的世界杯要开始啦，牛牛作为一个球迷，当然不会放过去开幕式现场的机会。但是牛牛一个人去又觉得太过寂寞，便想叫上了他的n个小伙伴陪他一起去莫斯科(一共n+1人)。当牛牛开始订开幕式的门票时，发现门票有m种套餐，每种套餐需要花费x元，包含y张门票，每张门票也可以单独购买，此时这张门票的价格为k元。请问牛牛要怎样选择购买门票，使得他花费的钱最少。(每种套餐可以购买次数没有限制)。

输入描述:

第一行输入三个数字n(0≤n≤999)、m(1≤m≤1000)和k(1≤k≤100000)
接下来m行，每行输入两个数字x_i(1≤xi≤100000)和yi(2≤yi≤1000), 表示套餐的价格和套餐内包含的门票数量。

输出描述:

输出牛牛至少要花费的钱的数量。

示例1

输入

2 2 5
6 2
13 3

输出

算法知识视频讲解

Java

求天求地求Offer

//基本思路：刚开始不整理，就是将买几张票的钱数先存在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]);
    }
}

发表于 2018-07-03 22:50:28 回复(0)

Java

刘禅挥泪斩孔明

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]);
  }
}

编辑于 2018-06-29 12:05:09 回复(0)