25561: 2022决战双十一
brute force, dfs, http://cs101.openjudge.cn/practice/25561/
又是一年双十一，某猫一如既往推出一系列活动，去年尝到甜头的Casper希望今年继续。今年他希望从m个店铺中购买n个商品，每个商品可能在一个或多个店铺中以不同的标价出售。此次跨店满减的活动升级为每满300减50，此外每个店铺也可能有多张不同档位的店铺券”q-x“，希望你能够帮助Casper算出他最少花多少钱买到这n个商品（每个商品只买一件）
注意，每一家店铺的店铺券只能用一张，对于任意一张店铺券”q-x“，他表示在当前商铺购买的所有商品标价达到q时，最终应付款可以减x。
而跨店满减活动可以叠加使用，它是指所有商品标价之和每满300，可以减去50。
输入
第一行为两个整数 n 和 m ，分别表示有 n 个商品和 m 个店铺（1 < n < 9，1 < m < 6）
接下来 n 行分别是 n 个商品的相关价格，其中第 i 行表示出售商品 i 的店铺及其标价，具体形式为s_i: p(i,s_i)，其中 s_i 为店铺编号（1 <= s_i <= m），p(i,s_i) 为这个店铺关于这件商品的报价，每个店铺的标价用空格分开。
最后 m 行中，每一行表示一个店铺的优惠券，用 q-x 表示，满足 q >= x，每张优惠券间用空格分开。
输出
最低的成交价
样例输入
Sample Input1:
2 2
1:100 2:120
1:300 2:350
200-30 400-70
100-80
Sample Output1:
260样例输出
Sample Input2:
3 2
1:100 2:120
1:300
2:180
100-20 200-50 300-90 400-140
200-100 250-80
Sample Output2:
310提示
tags: brute force, dfs
样例1：260 = (120 - 80) + (300 - 30) - 50 商品1在店铺2购买，商品2在店铺1购买，总的标价为420，通过满减可以减50；在店铺1的标价之和为300，可以用200-30的店铺券，在店铺2的标价之和为120，可以用100-80的店铺券
样例2：310 = (300 - 90) + (120 + 180 - 100) - 100 商品1在店铺2购买，商品2在店铺1购买，商品3在店铺2购买，总的标价为600，通过满减可以减100；在店铺1购买物品的标价之和为300，可以用300-90的店铺券，店铺2标价之和为300，可以用200-100的店铺券
来源: 2022fall, zzr
dfs暴力枚举
python
# 张俊龙，工学院
result = float("inf")
n, m = map(int, input().split())
store_prices = [input().split() for _ in range(n)]
you= [input().split() for _ in range(m)]
la=[0]*m
def dfs(i,sum1):
global result
if i==n:
jian=0
for i2 in range(m):
store_j=0
for k in you[i2]:
a,b=map(int,k.split('-'))
if la[i2]>=a:
store_j=max(store_j,b)
jian+=store_j
result=min(result,sum1-(sum1//300)*50-jian)
return
for i1 in store_prices[i]:
idx,p=map(int,i1.split(':'))
la[idx-1]+=p
dfs(i+1,sum1+p)
la[idx-1]-=p
dfs(0,0)
print(result)python
# 2022决战双十一, http://cs101.openjudge.cn/practice/25561/
result = float("inf")
n, m = map(int, input().split())
store_prices = [input().split() for _ in range(n)]
coupons = [input().split() for _ in range(m)]
def dfs(store_prices, coupons, items=0, total_price=0, each_store_price=[0] * m):
global result
if items == n:
# 查看店铺券使用情况
coupon_price = 0
for i in range(m):
# 在这个店铺可以减的金额
#store_p = max([int(coupon.split('-')[1]) for coupon in store_coupon if each_store_price[i] >= int(coupon.split('-')[0])], default=0)
store_p = 0
for coupon in coupons[i]:
a, b = map(int, coupon.split('-'))
if each_store_price[i] >= a:
store_p = max(store_p, b)
coupon_price += store_p
result = min(result, total_price - (total_price // 300) * 50 - coupon_price)
return
for i in store_prices[items]:
idx, p = map(int, i.split(':'))
each_store_price[idx - 1] += p
dfs(store_prices, coupons, items + 1, total_price + p, each_store_price)
each_store_price[idx - 1] -= p
dfs(store_prices, coupons)
print(result)python
# 2023fall-cs101: Stretcher 薛晋
def plans(n, price, count, all_plans, plan): # 递归列出所有购买方案
if count == n + 1:
all_plans.append(plan[:])
return
for i in price[count].keys():
plan.append(i)
plans(n, price, count + 1, all_plans, plan)
plan.pop()
return
def buy(n, m, price, coupon):
all_plans = list() # 列出所有购买方案
plans(n, price, 1, all_plans, [])
# for i in all_plans:
# print(i)
final_price = list() # 每个方案的最终价格
for plan in all_plans: # 对每个购买方案
totals_rsp = list() # 每个店铺的总价
prices = [price[i][plan[i - 1]] for i in range(1, n + 1)] # 每个商品的价格
total = sum(prices) # 所有商品的总价
total -= total // 300 * 50 # 跨店满减
for i in range(1, m + 1): # 对每个店铺
prices_rsp = [price[j + 1][plan[j]]
for j in range(n) if plan[j] == i] # 每个商品在该店铺的价格
totals_rsp.append(sum(prices_rsp)) # 该店铺的总价
store = 0
for total_rsp in totals_rsp:
store += 1
discount = 0
for j in coupon[store]:
if total_rsp >= j[0]:
discount = max(j[1], discount)
total -= discount
final_price.append(total)
# print(final_price)
return min(final_price)
n, m = map(int, input().split())
price = dict()
coupon = dict()
for i in range(n):
price_i = dict()
price_raw = list(input().split())
for j in price_raw:
price_i[int(list(j.split(':'))[0])] = int(list(j.split(':'))[1])
price[i + 1] = price_i
for i in range(m):
coupon_i = list()
coupon_raw = list(input().split())
for j in range(len(coupon_raw)):
coupon_i.append(tuple(map(int, coupon_raw[j].split('-'))))
coupon[i + 1] = coupon_i
# print(n, m, price, coupon)
print(buy(n, m, price, coupon))最多有
python
# 卢殷文 24物院
import itertools
inf=10**9
n,m=map(int,input().split())
p=[[inf]*m for _ in range(n)]
q=[[] for _ in range(m)]
for i in range(n):
*sold,=input().split()
for s in sold:
si=int(s[0])-1
pi=int(s[2:])
p[i][si]=pi
for j in range(m):
*quan,=input().split()
for s in quan:
a,b=map(int,s.split('-'))
q[j].append([a,b])
plans=itertools.product(range(m),repeat=n)
final_money=inf
for plan in plans:
money=[0]*m
for i in range(n):
money[plan[i]]+= p[i][plan[i]]
final=sum(money)
final-=final//300*50
for j in range(m):
maxq=0
for qq in q[j]:
if money[j]>=qq[0]:
maxq=max(qq[1],maxq)
final-=maxq
if final<final_money:
final_money=final
print(final_money)有点像八皇后的感觉，有点难写的可能是dfs终点时钱数和折扣的计算，采用的方法是提前建一个shop列表把此前在每个店铺花的钱都存起来。
python
# 李承容 2400011499 物理学院
def dfs(goo,shops,cou):
global mn
if goo==[]:
cheaper=[0]*m
for y in range(m):
for x in cou[y]:
if shops[y]>=x[0]:
cheaper[y]=max(cheaper[y],x[1])
q=sum(shops)//300
mn=min(sum(shops)-sum(cheaper)-q*50,mn)
return
for i in range(len(goo[0])):
shops[goo[0][i][0]-1]+=goo[0][i][1]
dfs(goo[1:len(goo)],shops,cou)
shops[goo[0][i][0]-1]-=goo[0][i][1]
n,m=map(int,input().split())
good=[[] for _ in range(n)]
coupon=[[] for _ in range(m)]
for i in range(n):
prodx=list(input().split())
good[i]=[tuple(map(int,x.split(":"))) for x in prodx]
for j in range(m):
cou=list(input().split())
coupon[j]=[tuple(map(int,y.split("-"))) for y in cou]
mn=float("inf")
dfs(good,[0 for _ in range(m)],coupon)
print(mn)