NC14526 购物
题目链接
题目
题目描述
在遥远的东方,有一家糖果专卖店。
这家糖果店将会在每天出售一些糖果,它每天都会生产出 \(m\) 个糖果,第i天的第j个糖果价格为 \(C[i][j]\) 元。
现在的你想要在接下来的 \(n\) 天去糖果店进行选购,你每天可以买多个糖果,也可以选择不买糖果,但是最多买 \(m\) 个。(因为最多只生产 \(m\) 个)买来糖果以后,你可以选择吃掉糖果或者留着之后再吃。糖果不会过期,你需要保证这n天中每天你都能吃到至少一个糖果。
这家店的老板看你经常去光顾这家店,感到非常生气。(因为他不能好好睡觉了)于是他会额外的要求你支付点钱。具体来说,你在某一天购买了 \(k\) 个糖果,那么你在这一天需要额外支付 \(k^2\) 的费用。
那么问题来了,你最少需要多少钱才能达成自己的目的呢?
输入描述
第一行两个正整数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 , 所有输入的数均 ≤ \(10^6\) 。
题解
知识点:线性dp,贪心。
设 \(dp[i][j]\) 代表考虑到第 \(i\) 天共买了 \(j\) 个糖。
因为我们需要最小费用,因此对于每一天,我们肯定从价格最少的糖开始选择,因此先对每一天的糖排序。再用前缀和 \(sum[i][j]\) 代表第 \(i\) 天前 \(j\) 个糖的本身费用。
对于 \(dp[i][j]\) ,可以从前一天买了 \(j-k\) 个糖加上第 \(i\) 天 \(k\) 个糖的总费用( \(k\) 可以为 \(0\)),即 \(\min \limits_{0 \leq k \leq j} dp[i-1][j-k] + sum[i][k] + k^2\) ,于是有转移方程:
这道题的边界认真处理有点绕,但实际上不需要这么严格。
首先全部赋值无穷大,方便处理。
对于第 \(i\) 天:
- \(j\) 最小值是 \(i\) 开始,因为每天必须吃一颗。
- \(j\) 的最大值是 \(\min (n,im)\) ,但实际上写只需要小于等于 \(n\),因为超出 \(im\) 部分今天根本不可能买得到,只会从无穷大转移。
- \(k\) 的最小值是 \(\max (0,j-(i-1)m)\) ,因为前面全买了也就 \((i-1)m\) 颗糖,不可能再多,于是 \(j-(i-1)m\) 是今天至少买的糖,但实际上 \(k\) 只要写大于等于 \(0\) 即可,因为 \(k\) 小于 \(j-(i-1)m\) 时,\(j-k > (i-1)m\) 比上一轮能买到都多,只可能从无穷大转移,同2。
- \(k\) 的最大值是 \(\min(j,m)\),因为今天要买到总共 \(j\),那么今天不可能买了超过 \(j\) ,而每天不可能买超过 \(m\) 。
其中 1,4 是必须的,2,3 是可以不严格的。
时间复杂度 \(O(nm\log m + n^2m)\)
空间复杂度 \(O(nm)\)
代码
#include <bits/stdc++.h>
using namespace std;
int a[307][307], dp[307][307];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++)
cin >> a[i][j];
sort(a[i] + 1, a[i] + m + 1);
}
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
a[i][j] += a[i][j - 1];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
///只要数组不越界,并且不到a的无意义范围就行(给a其他地方赋值无穷大也可以)
///因为如果用dp中没有经过的地方传递会出现无穷大,如果之后经过一定会被替代,不影响结果
for (int i = 1;i <= n;i++) {
for (int j = i;j <= min(n, i * m);j++) { ///每天至少吃一个从i开始,但多买可以<=n就行,如果超出了i*m只会从无穷大转移
for (int k = max(0, j - (i - 1) * m);k <= min(m, j - i + 1);k++) {///从k=0到min(m,j)开始就行,小于(i-1)*m或者大于j-i+1也只会从无穷大转移
dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + a[i][k] + k * k);
}
}
}
cout << dp[n][n] << '\n';
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int a[307][307], dp[307][307];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++)
cin >> a[i][j];
sort(a[i] + 1, a[i] + m + 1);
}
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
a[i][j] += a[i][j - 1];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
///只要数组不越界,并且不到a的无意义范围就行(给a其他地方赋值无穷大也可以)
///因为如果用dp中没有经过的地方传递会出现无穷大,如果之后经过一定会被替代,不影响结果
for (int i = 1;i <= n;i++) {
for (int j = i;j <= min(n, i * m);j++) { ///每天至少吃一个从i开始,但多买可以<=n就行,如果超出了i*m只会从无穷大转移
for (int k = max(0, j - (i - 1) * m);k <= min(m, j - i + 1);k++) {///从k=0到min(m,j)开始就行,小于(i-1)*m或者大于j-i+1也只会从无穷大转移
dp[i][j] = min(dp[i][j], dp[i - 1][j - k] + a[i][k] + k * k);
}
}
}
cout << dp[n][n] << '\n';
return 0;
}
上一篇: 动态增删表格
推荐阅读
-
小米商城(购物车页面和统计效果实现)
-
NC14526 购物
-
开发友好型 Macbook_2020 MacBook 购物:如何选择第一台苹果笔记本电脑
-
谷物购物中心 - 个人笔记(基金会 II)
-
小型内衣清洗机哪个牌子好?私人共享的六个购物技巧
-
微信 "扫一扫 "物联网,全面揭秘 "扫一扫 "背后的扫盲技术!-1.1 扫一扫感知物体是做什么的? 1.1 微信扫一扫是做什么的? 扫一扫识物是指以图片或视频(商品图片:鞋/包/美妆/服饰/家电/玩具/图书/食品/珠宝/家具/其他商品)为输入媒介,挖掘微信内容生态中的有价值信息(电商+百科+资讯,如图1所示),并展示给用户。这里的电商基本涵盖了微信小程序覆盖上亿SKU的全量优质电商,可以支持用户货比N家并直接下单购买,百科和资讯则聚合了微信内的头部自媒体如搜狗、搜搜、百度等,向用户展示和分享拍摄商品相关的内容资讯。 图 1 扫一扫识别功能示意图 欢迎大家更新iOS新版微信→扫一扫→识货,亲自体验,也欢迎大家通过识货界面的反馈按钮向我们提交反馈意见。 扫一扫识物实景图展示 1.2 扫一扫识物有哪些使用场景? 扫一扫识物的目的是为用户访问微信内部生态内容开辟一个新窗口,以用户扫图片为输入形式,为用户提供微信生态内容中的百科、资讯、电商等作为展示页面。除了用户熟悉的扫一扫操作外,我们还将进一步拓展长按操作,让用户更方便地进行扫一扫操作。"扫一扫知事 "的落地场景主要涵盖三大部分: a. 科普知识: a.科普知识。用户通过扫一扫,可以在微信生态圈中获取该对象的百科、资讯等常识或趣闻,帮助用户更好地了解该对象; b.购物场景。同样的搜索功能支持用户看到喜欢的商品立即检索到微信小程序电商中的同款商品,支持用户即扫即购; c.广告场景。扫一扫识别物体可以辅助公众号文章、视频更好地理解其中蕴含的图片信息,从而更好地投放匹配广告,提高点击率。 1.3 Sweep Sense 为 Sweep 家族带来了哪些新技术? 对于扫一扫来说,大家耳熟能详的应该就是扫一扫二维码、扫一扫小程序码、扫一扫条形码、扫一扫翻译了。无论是各种形式的编码还是文字字符,都可以看作是图片的一种特定编码形式,而物的识别则是对自然场景图片的识别,这对于扫一扫家族来说是一个质的飞跃,我们希望从物的识别入手,进一步拓展扫一扫对自然场景图片的理解能力,比如扫酒、扫车、扫植物、扫人脸等服务,如下图3所示。 图 3 Sweep 家族
-
PHP 开发商城购物车功能详解
-
家庭网上购物项目(Ajax 验证用户名 + 上传图片)
-
❤重点❤】【牛客网 - 华为整机测试】HJ16 购物清单 - 动态规划
-
产品列表页面购物车的 JavaScript 开发