牛客-购物(DP/贪心）

购物

https://ac.nowcoder.com/acm/contest/6877/A

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

输入描述:
第一行两个正整数n和m，分别表示天数以及糖果店每天生产的糖果数量。
接下来n行（第2行到第n+1行），每行m个正整数，第x+1行的第y个正整数表示第x天的第y个糖果的费用。
输出描述:
输出只有一个正整数，表示你需要支付的最小费用。
示例1
输入

3 2
1 1
100 100
10000 10000

输出

107

示例2
输入

5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

输出

10

备注:
对于100%的数据，1 ≤ n, m ≤ 300 , 所有输入的数均 ≤ 106。

题目要求最低价格，那么首先可对每天的糖果的价格a[i][j]由低到高进行排序，并且保留第 i 天前 j 颗糖果的价格 sum[i][j].

动规：有两种推导思路：

一， dp[i][j]: 表示第 i天总共买 j个糖果的最低价格，那么dp[i][j]=min{dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k)};

二， dp[i][j]: 表示第i天 吃完后手里有 j个糖果需要的最低价格，则dp[i][j]=min{dp[i-1][j+1-k]+sum[i][k]+k*k};

贪心：如果只要求n天买n颗糖果的最低价格，那么可以对n天的糖果的价格由小到大进行排序，然后取前n个即可，但本题增加了额外条件：

你在某一天购买了 k 个糖果，那么你在这一天需要额外支付 k2 的费用。那么糖果的价格就受到当天购买数量的影响了，这就要考虑能不能去除掉这个影响。由于要使得花费的价格最低，则每颗糖的购买就有了先后次序，又购买t颗糖要额外花费 tt ,购买 t+1 颗要额外花费 (t+1)(t+1)，则购买第 t+1 颗糖时要额外花费 (t+1)(t+1)-tt 即 2t+1 ，那么只要把第 t 颗糖的价格提高 2t+1 j就可以去除掉这个影响。

你需要保证这n天中每天你都能吃到至少一个糖果。这个要求则不能够取最小的 n 颗糖果了，那么可以用优先队列保存前i天的所有糖果价格，每天取最小的一颗糖果，在把已取的糖果去掉即可。

DP 示例代码1

#include<iostream>
#include<algorithm>
using namespace std;
const int INF=1e9+7;
const int MAX_N=305;
const int MAX_M=305; 
int n,m;
int a[MAX_N][MAX_M];
int sum[MAX_N][MAX_M];
//dp[i][j]: 第 i天总共买 j个糖果的最低价格
int dp[MAX_N][MAX_N];
int main()
{
 ios::sync_with_stdio(false);
 cin.tie(0);

 cin>>n>>m;
 for(int i=0;i<=n;++i)
     for(int j=1;j<MAX_N;++j)
         dp[i][j]=sum[i][j]=INF;
 for(int i=1;i<=n;++i)
 {
     for(int j=1;j<=m;++j)
         cin>>a[i][j];
     sort(a[i]+1,a[i]+m+1);
     for(int j=1;j<=m;++j)
         sum[i][j]=sum[i][j-1]+a[i][j];
 }

 for(int i=1;i<=m;++i)
     dp[1][i]=sum[1][i]+i*i;
 for(int i=2;i<=n;++i)
 {
     for(int j=i;j<=n;++j)
         for(int k=i-1;k<=j;++k)
             dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k));
 }
 cout<<dp[n][n]<<endl;

 return 0;
}

　DP示例代码２

#include<iostream>
#include<algorithm>
using namespace std;

const int INF=1e9+7;
const int MAX_N=305;
const int MAX_M=305;
int n,m;
int a[MAX_N][MAX_M];
int sum[MAX_N][MAX_M];
//dp[i][j]: 第i天 *吃完后*手里有 j个糖果需要的最低价格 
int dp[MAX_N][MAX_N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<=n;++i)
    {
        for(int j=0;j<MAX_N;++j)
            dp[i][j]=sum[i][j]=INF;
        sum[i][0]=0;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            cin>>a[i][j];
        sort(a[i]+1,a[i]+m+1);
        for(int j=1;j<=m;++j)
            sum[i][j]=sum[i][j-1]+a[i][j];
    }

    for(int i=0;i<=m;++i)
        dp[1][i]=sum[1][i+1]+(i+1)*(i+1);
    for(int i=2;i<=n;++i)
        for(int j=0;j<=n;++j)
            for(int k=0;k<=j+1&&k<=m;++k)
                dp[i][j]=min(dp[i][j],dp[i-1][j+1-k]+sum[i][k]+k*k);
    cout<<dp[n][0]<<endl;

    return 0;
}

贪心做法

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

const int MAX_N=305;
const int MAX_M=305;
int n,m,ans;
int a[MAX_N][MAX_M];
priority_queue<int,vector<int>,greater<int>> Q;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
            cin>>a[i][j];
        sort(a[i],a[i]+m);
        for(int j=0;j<m;++j)
            a[i][j]+=2*j+1;
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
            Q.push(a[i][j]);
        ans+=Q.top();
        Q.pop();
    }
    cout<<ans<<endl;

    return 0;
}

题解，来自：https://blog.csdn.net/C_13579/article/details/78820195