【每日一题】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

相关推荐

zYvv:双一流加大加粗再标红,然后广投。主要是获奖荣誉不够,建议开始不用追求大厂,去别的厂子刷下实习。
点赞 评论 收藏
分享
太难了,双9bg也被刷
投递韶音科技等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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