讨论/面试考题/请教一道line的笔试题/
请教一道line的笔试题

主要是当时个人想法是还是深搜加优化,不过总觉得哪里不对导致大的数据过不了,所以想请教下思路

原题的大概意思是
总共有n张桌子和m组客人以及好感度扣除计算用的参数x和y
a[n] 则表示每张桌子能够坐的人数
b[m] 则表示每一组有多少人
然后需要将客人分配到桌子上去或者拒绝掉
分配的时候不能不同组客人分到一起

那么会根据分配或者拒绝掉减去一定的客人好感度
好感度扣除规则是:
1如果一组客人全部分在一张桌子上那么扣除好感度为:0
2如果拒绝掉了第i组客人,那么好感度扣除为:x*b[i] (意思就是参数x乘以人数)
3如果把一组客人分在了k张桌子上,那么好感度扣除为(k-1)*y

求解扣除的好感度最少为多少

输入格式的样例为
n m x y
a[1] a[2] ... a[n]
b[1] b[2] ... b[m]

例子1:
4 2 5 3
4 5 1 1
7 3

答案是6
因为把7人的分在(5,1,1)这三桌里
剩下的3人分在(4)这一桌子里

例子2:
4 2 2 16
4 5 1 1
7 3
答案是14
把7人的给拒绝了
然后3人的给分在(5)的桌子里

展开讨论
TAL发起于 2020-05-09
最近编辑于 2020-05-09
共 3 个讨论

有特殊的条件吗?

数据规模20的话是O(2^n)算法,所以大概真的是深搜,就看你怎么优化了

暴力动态规划复杂度是O(m3n)O(m3^n),可能有什么优化方法。