【每日一题】8月4日题目精讲—购物

购物

https://ac.nowcoder.com/acm/problem/14526

思路:
首先我们每天肯定都是按照价格从低到高买糖果,所以决策只需要关注当前天买了多少个。
f[i][j]代表前i天已经买了j颗糖果的最小花费,枚举第i天买了多少糖果。
f[i][j] = min(f[i-1][k] + sum[i][i-k] + (j-k)*(j-k)); (k从i-m到i-1枚举)
普通的背包问题,注意边界。。。。。。。。。。。。
用到前缀和
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
//#include<bits/stdc++.h>
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f;
typedef long long ll;
ll gcd(ll a, ll b)
{
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
	return a * b / (gcd(a, b));
}
#define PII pair<int,int>
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 7;
int qmi(int a, int k, int p)		//快速幂模板
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (ll)res * a % p;
		k >>= 1;
		a = (ll)a * a % p;
	}
	return res;
}
///////////////////////////////////////////////////////////
int dp[1005][1005];
int s[1005][1005];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cin >> s[i][j];
		sort(s[i] + 1, s[i] + 1 + m);
		for (int j = 1; j <= m; j++)
			s[i][j] += s[i][j - 1];
	}
	memset(dp, inf, sizeof(dp));
	dp[0][0] = 0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=min(i*m,n);j++)
			for (int k = i - 1; k <= j; k++) {
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + s[i][j - k] + (j - k) * (j - k));
			}
	cout << dp[n][n] << endl;
	return 0;
}



全部评论
这代码好像也错了,兄弟,你可以跑一下这组数据: 7 5 174 303 346 131 219 170 13 475 322 84 130 464 469 417 21 11 446 176 447 24 166 339 277 275 180 440 47 263 180 408 279 43 281 216 339 答案是299 错在第三重循环k应该从max(i-1,j-m)开始才对
点赞 回复 分享
发布于 2020-08-25 17:43

相关推荐

不愿透露姓名的神秘牛友
07-24 13:35
点赞 评论 收藏
分享
06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
07-23 11:23
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务