首页 > 试题广场 >

牛牛与世界杯门票

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

热度指数：1212 时间限制：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

输出

算法知识视频讲解

JavaScript

w布响丸辣

/*世界杯门票
这个题可以看做是一个背包问题，人的个数相当于背包的容量，票的价格相当于价值，dp[i]表示买到i张票时的最小花费为dp[i]，最后dp[n]即为买到n张票时的最小花费
*/
var line1 = readline().split(' ');
var n = parseInt(line1[0]),
    m = parseInt(line1[1]),
    k = parseInt(line1[2]);
    n++;
var dp = []; 
for(var i=0;i<=n;i++){     dp[i] = i*k;
}

for(var i=0;i<m;i++){
    var line2 = readline().split(' ');
    for(var j=1;j<=n;j++){
        if(j-line2[1]>=0){
            dp[j] = Math.min(dp[j],dp[j-line2[1]]+parseInt(line2[0]));
        }else{
            dp[j] = Math.min(dp[j],parseInt(line2[0]));
        }
    }
}
print(dp[n]);

发表于 2018-09-17 16:20:14 回复(0)