购物算法（DP最优购买花费最小）_C/C++

购物算法（DP最优购买花费最小）

思路

最优值问题，我们考虑 $dp$ ， $dp[i][j]$ 表示前 $i$ 天已经购买了 $j$ 个糖果的花费最小值，显然 $dp[i][j]$ 可以从 $dp[i - 1][k]$ 转移过来，具体转移过程看代码注释部分吧。

对于答案我们显然是在第 $n$ 天刚好购买了 $n$ 个糖果，这样是最优的，对于每一天购买糖果，我们一定是优先选择花费更小的，这样才能保证最优值.

代码

/*
  Author : lifehappy
*/ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1 using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f; inline ll read() { ll f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return f * x; } const int N = 310; ll a[N][N], n, m, dp[N][N]; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); n = read(), m = read(); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { a[i][j] = read(); } sort(a[i] + 1, a[i] + 1 + m);//对糖果价钱排个序 for(int j = 1; j <= m; j++) {//求个前缀和方便后面的dp。 a[i][j] += a[i][j - 1]; } } memset(dp, 0x3f, sizeof dp); dp[0][0] = 0; for(int i = 1; i <= n; i++) {//按照套路两重循环i, j分别代表天数跟糖果总数。 for(int j = i; j <= min(n, i * m); j++) {//因为每一天一定要有糖果，所以一定是第i天最少要有i个糖果。 //当天获得的最大糖果数量是min(n, i * m)，这个一定要保证，因为最多只要n个，当天最多只能得到i * m个 for(int k = i - 1; k <= min(n, (i - 1) * m) && k <= j; k++) {//前一天转移过来的最少也要有i - 1个糖果， //这里考虑转换的时同样的要考虑上一步转移过来的是否符合要求，所以规定数量 //k <= j && k <= 前几天糖果数量总和 && k <= n 我们需要的最多糖果。 dp[i][j] = min(dp[i][j], dp[i - 1][k] + a[i][j - k] + (j - k) * (j - k)); } } } cout << dp[n][n] << endl; return 0; }