【每日一题】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枚举）
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;
}
查看30道真题和解析
投递快手等公司10个岗位