世界杯买票

发表于

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def start():
    line = raw_input().strip()
    if line == '':
        return
    line = line.split(' ')
    num = int(line[0])+1
    mnum = int(line[1])
    k = int(line[2])
    dp = []
    for i in xrange(num):
        dp.append((i+1)*k)


    for i in xrange(mnum):
        line = raw_input().strip()
        if line == '':
            return
        x = int(line.split(' ')[0])
        y = int(line.split(' ')[1])
        for i in xrange(1,num+1):
            if i - y >0:
                dp[i-1] = min(dp[i-1],dp[i-1-y]+x)
            else:
                dp[i-1] = min(dp[i-1],x)
    print dp[num-1]


if __name__ == '__main__':
    start()