首页 > 试题广场 >

购物

[编程题]购物
在遥远的东方，有一家糖果专卖店。
这家糖果店将会在每天出售一些糖果，它每天都会生产出m个糖果，第i天的第j个糖果价格为C[i][j]元。
现在的你想要在接下来的n天去糖果店进行选购，你每天可以买多个糖果，也可以选择不买糖果，但是最多买m个。（因为最多只生产m个）买来糖果以后，你可以选择吃掉糖果或者留着之后再吃。糖果不会过期，你需要保证这n天中每天你都能吃到至少一个糖果。
这家店的老板看你经常去光顾这家店，感到非常生气。（因为他不能好好睡觉了）于是他会额外的要求你支付点钱。具体来说，你在某一天购买了 k 个糖果，那么你在这一天需要额外支付 k2 的费用。

那么问题来了，你最少需要多少钱才能达成自己的目的呢？


输入描述:
第一行两个正整数n和m，分别表示天数以及糖果店每天生产的糖果数量。
接下来n行（第2行到第n+1行），每行m个正整数，第x+1行的第y个正整数表示第x天的第y个糖果的费用。


输出描述:
输出只有一个正整数，表示你需要支付的最小费用。
示例1

输入

3 2 
1 1
100 100 
10000 10000

输出

107
示例2

输入

5 5
1 2 3 4 5
2 3 4 5 1 
3 4 5 1 2 
4 5 1 2 3 
5 1 2 3 4

输出

10

备注:
对于100%的数据，1 ≤ n, m ≤ 300 , 所有输入的数均 ≤ 106。
算法知识视频讲解
开通博客
头像 sunrise__sunrise
发表于 2020-08-04 10:52:36
题目意思： Solution #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include < 展开全文
去ta的博客 赞 (4) 回复(2) 收起
头像 sunsetcolors
发表于 2020-08-03 21:32:55
购物 题目地址： https://ac.nowcoder.com/acm/problem/14526 基本思路： 考虑,设表示处理到第天,买了个糖果的最小花费;首先我们在每一天里,肯定是优先买价格更低的糖果,因此我们先对每一天排序,并且求一个前缀和;然后我们考虑如何转移,首先我们第天的合法糖 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 江三
发表于 2020-08-05 20:39:09
一.题意 有 天，每天可购买 个糖，不同时间、不同的糖有不同价格。每天购买 个糖有额外代价 。第 天结束时累计购买数达到 。求最小花费。 二.题解 参考一个题解： https://blog.nowcoder.net/n/aec8d532559a4fc4bd1561da0ec1 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 zzugzx
发表于 2020-08-03 20:49:14
题目链接 题意：题解：AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #def 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 阿威敲快乐
发表于 2023-11-04 22:18:09
使用优先对列的思想购买n天一共购买n个糖果 先对每天买糖果的花费进项排序 并将每天买糖果的额外花费分摊到每一个糖果中，最后取出从大到小排序的队列的顶部n个元素之和即为买糖果的最小花费 #include<bits/stdc++.h> using namespace std; const i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-11-16 21:58:33
动态规划问题，一开始看到每天要买的糖果数还不一样，而且每个糖果还有他自己不同的价格。直接就想到了状压DP。 但本题要求花费最小，而对于某一天买k个糖果来说花费最小其实就是从价格低的糖果来买就行了。那么某一天如何选糖果的问题就这样简答的解决了。 那么状态数组为：dp[i][j]。i代表天数 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zqy1018_
发表于 2020-08-04 09:01:40
题目大意 有 天，每天可购买 个糖，不同时间、不同的糖有不同价格。每天购买 个糖有额外代价 。须保证第 天结束时累计购买数达到 。问最小代价。 题解 写了一个朴素的二维 DP，预先对每一天的糖价格排序，然后设 为第 天结束时买了 个糖的最小代价。则 其中 表示前 天最小的 个糖的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 horz
发表于 2020-08-04 10:18:55
做完今天的N1，然后发现这不是一样的题目吗？？？ 题意 我们每天可以最多购买m个糖果，连续买 k 个需要额外支付 。保证每天吃一个糖，求买n个糖果的最少代价。 分析 我们定义dp[i][j]，表示前i天买了j颗糖的代价。 我们对 m 颗糖可以贪心一下，一定是买更便宜的糖。 然后枚举今天买几颗即可。 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-08-09 22:16:59
题意：有一家糖果店，每天可以生产m颗糖果，你在接下来n天会去买糖果，你每天必须吃一颗糖果，你买的糖果可以保存以后吃，你每天买糖果还需要额外花当天买的糖果个数的平方的钱，求这n天你最少花多少钱？ 思路：dpdp[i][j]表示前i天买j颗糖果的最少花费。sum[i][o]表示第i天买o颗糖果的糖果花费 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Infinite_Light
发表于 2025-01-22 16:23:31
链接：https://ac.nowcoder.com/acm/contest/24213/1015 来源：牛客网 题目描述 在遥远的东方，有一家糖果专卖店。 这家糖果店将会在每天出售一些糖果，它每天都会生产出m个糖 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

动态规划
上传者：牛客301599号
难度：
0条回答 1浏览

热门推荐

通过挑战的用户

查看代码

相关试题

购物

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号