题号 NC14526
名称 购物
来源 牛客练习赛7
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

先说dp做法：
首先我们每天肯定都是按照价格从低到高买糖果，所以决策只需要关注当前天买了多少个。
f[i][j]代表前i天已经买了j颗糖果的最小花费，枚举第i天买了多少糖果。
f[i][j] = min(f[i-1][k] + sum[i][j-k] + (j-k)*(j-k)); （k从i-m到i-1枚举）
但是事实上可以更简单:
因为每天我们都按照价格从低到高买糖果，排完序之后如果我们第i天买了第x个糖果，前
x-1个是肯定要买的——只买前x-1个糖果花了sum[i][x-1] + (x-1)^2的钱，买前x个糖果花sum[i][x] + x^2的钱，相减就会发现买第x个糖果的钱为a[i][x]+2x-1（相当于把附加的钱按照贡献分给每个糖果），其实只和他自己的价格以及在自己那一天是第几个买有关，和他前面的糖果都是多少钱无关，且原来排在花钱少的糖果最终花钱还是少（如果我们选了第x个糖果那么他前面的糖果肯定都选上了）。这样，最后吃掉的n个糖果一定是a[i][x]+2x-1最小的n个（真正买的时候不是按照大小关系顺序而是按照日期），所以直接贪心就可以了——先把每天的糖果排序，排好之后给他们加上排位带来的附加价格(2x-1)，然后按照加上了附加价格之后的价格把每天可以买的糖果放入容器里，再把容器中价格最小的糖果拿出来（这个容器可以用堆也可以用set等）。
这里说明一下能用贪心的原因：
附加价格不会影响原来的选择顺序，对于本题来说即越排在后面附加得越多（如果原来的选择顺序是从大到小，那么自然要保证前面的增量大）
每天的选择独立，昨天选了几个和今天的选择没关系（如果题面要求每天必须比前一天选得多之类的自然只能dp了）

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目9月1日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴