购物_牛客博客

题目描述

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

输入描述:

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

输出描述:

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

题解

首先对于某一天里的糖果，我们肯定是选择便宜的划算

那我们先对某一天里的糖果花费进行排序，然后进行dp

以 $dp[i][j]$ 表示前 $i$ 天买 $j$ 个糖果的最小代价，那么枚举第 $i+1$ 天买的糖果数量即有转移 $dp[i+1][j+k]=min(dp[i+1][j+k],dp[i][j]+k^2+sum[i+1][k]),j≥i,j+k≥i+1$

其中 $sum[i][j]$ 表示在第 $i$ 天买 $j$ 个糖果所需的最小代价， $dp[n][n]$ 即为答案

由于我们只需要买n个糖果就好了，开数组的时候开成dp[350][350]即可，不然会爆空间

时间复杂度 $O(n^3)$

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
const int mod=1e9+7;
vector<int> v[350];
int n,m;
ll dp[350][350];
ll sum[350][350];
////////////////////////////////////////////////////////////////////////
int main(){
    n=gn(),m=gn();
    repi(i,1,n){
        repi(j,1,m){
            v[i].pb(gn());
        }
        sort(all(v[i]));
        repi(j,1,m){
            sum[i][j]=sum[i][j-1]+v[i][j-1];
        }
    }
    memset(dp,0x3f,sizeof(dp));
    ll ans=1e18;
    dp[0][0]=0;
    repi(i,1,n){
        repi(j,i,min(n,i*m)){
            repi(k,i-1,min(n,min(j,(i-1)*m))){
                dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k));
            }
        }
        ans=min(ans,dp[i][n]);
    }
    print(ans);
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/