题解 | #购物#

购物

题目描述

在遥远的东方，有一家糖果专卖店。 这家糖果店将会在每天出售一些糖果，它每天都会生产出m个糖果，第i天的第j个糖果价格为C[i][j]元。 现在的你想要在接下来的n天去糖果店进行选购，你每天可以买多个糖果，也可以选择不买糖果，但是最多买m个。（因为最多只生产m个）买来糖果以后，你可以选择吃掉糖果或者留着之后再吃。糖果不会过期，你需要保证这n天中每天你都能吃到至少一个糖果。 这家店的老板看你经常去光顾这家店，感到非常生气。（因为他不能好好睡觉了）于是他会额外的要求你支付点钱。具体来说，你在某一天购买了 k 个糖果，那么你在这一天需要额外支付 k2 的费用。 那么问题来了，你最少需要多少钱才能达成自己的目的呢？

输入描述:

第一行两个正整数n和m，分别表示天数以及糖果店每天生产的糖果数量。 接下来n行（第2行到第n+1行），每行m个正整数，第x+1行的第y个正整数表示第x天的第y个糖果的费用。

输出描述:

输出只有一个正整数，表示你需要支付的最小费用。

解法一

首先一定要保证每天都有糖果吃，所以在第i天已经购买的糖果数一定要大于等于i，所以第一天一定要至少买一个糖果。要让最终的费用最低，那么每天的水果都要从小到大排序。我们可以发现，在第i天买j个糖果，除了这j个糖果本身的费用之外，还要付j*j 的额外费用，买(j + 1)个糖果要多付(2 * j - 1)的额外费用，那么我们就用一个优先队列来维护，优先队列中是每个糖果的本身费用+额外费用

#include <bits/stdc++.h>

using namespace std;
int c[310][310],n,m,res = 0;
priority_queue<int,vector<int>,greater<int>> q;

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin >> c[i][j];//每天生产m个糖果
        }
        sort(c[i] + 1,c[i] + 1 + m);
    }
    for(int i = 1;i <= n;i ++){
        int cnt = 1;
        for(int j = 1;j <= m;j ++){
            c[i][j] = c[i][j] + cnt;
            cnt += 2;
        }
    }
    for(int i = 1;i <= m;i ++){
        q.push(c[1][i]);
    }
    res += q.top();
    q.pop();
    for(int i = 2;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            q.push(c[i][j]);
        }
        res += q.top();
        q.pop();
    }
    cout << res << '\n';
    return 0;
}

解法二——动态规划

状态表示

f[i][j]表示前i天总共买了j颗糖果的最低费用

状态计算

利用第i天卖多少颗糖果最为状态划分的依据，取f[i][j]的最小值，注意：这里j要大于等于i,且k需满足j - k >= i - 1,k <= m

#include <bits/stdc++.h>

using namespace std;
int c[310][310],n,m,res = 0x3f3f3f3f,f[310][310];

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            cin >> c[i][j];//每天生产m个糖果
        }
        sort(c[i] + 1,c[i] + 1 + m);
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            c[i][j] = c[i][j] + c[i][j - 1];
        }
    }
    //f[i][j]表示到第i天时，一共买了j颗糖果
    memset(f,0x3f,sizeof f);
    for(int i = 1;i <= m;i ++){
        f[1][i] = c[1][i] + i * i;
    }
    for(int i = 2;i <= n;i ++){
        for(int j = i;j <= n;j ++){//到第i天时，一定要买大于等于i颗糖果，这样才能保证每天都有糖果吃
            for(int k = 0;k <= j - i + 1;k ++){//k表示第i天买k颗糖果
                if(k <= m) f[i][j] = min(f[i - 1][j - k] + c[i][k] + k * k,f[i][j]);
            }
        }
    }
    cout << f[n][n];
    return 0;
}