购物

购物

https://ac.nowcoder.com/acm/problem/14526

题意：n * m个糖果，每个糖果都有价格，小明需要花最少的钱保证每天都有糖果吃，而且每天不能购买超过m个糖果，每天买第j个糖果的价格是a[i][j]+j*j，问你最少花多少钱过n天？

思路：首先想到对每天的价格排序，贪心去取小的，但是你可能这一天相对于后几天都比较小，那我们该怎么办？n<=300 dp转移?显然可以🤣 复杂度O(n^3),挺好写的，不详细解释了，读者可以尝试这个思路完成，dp[i][j]表示第i天买了j个糖果的最小花费。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>p;
const int N=305;
int dp[N][N],sum[N][N],a[N][N];
int n,m;
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d",&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];
    }
    memset(dp,63,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<=min(j,(i-1)*m); k++) {
                dp[i][j]=min(dp[i][j],dp[i-1][k]+sum[i][j-k]+(j-k)*(j-k));
            }
        }
    }
    printf("%d\n",dp[n][n]);
}

考虑O(n^2log)的做法，
因为每天我们都按照价格从低到高买糖果，排完序之后如果我们第i天买了第x个糖果，前
x-1个是肯定要买的——只买前x-1个糖果花了sum[i][x-1] + (x-1)^2的钱，买前x个糖果花sum[i][x] + x^2的钱，相减就会发现买第x个糖果的钱为a[i][x]+2x-1（相当于把附加的钱按照贡献分给每个糖果），其实只和他自己的价格以及在自己那一天是第几个买有关，和他前面的糖果都是多少钱无关，且原来排在花钱少的糖果最终花钱还是少（如果我们选了第x个糖果那么他前面的糖果肯定都选上了）。这样，最后吃掉的n个糖果一定是a[i][x]+2x-1最小的n个（真正买的时候不是按照大小关系顺序而是按照日期），所以直接贪心就可以了——先把每天的糖果排序，排好之后给他们加上排位带来的附加价格(2x-1)，然后按照加上了附加价格之后的价格把每天可以买的糖果放入容器里，再把容器中价格最小的糖果拿出来（这个容器可以用堆也可以用set等）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>p;
const int N=305;
int dp[N][N],sum[N][N],a[N][N];
int n,m;
int main() {
    cin>>n>>m;
    int ans=0;
    multiset<int>s;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d",&a[i][j]);
        }
        sort(a[i]+1,a[i]+m+1);
        for(int j=1; j<=m; j++)s.insert(a[i][j]+2*j-1);
        ans=ans+*s.begin();
        s.erase(s.begin());
    }
    printf("%d\n",ans);
}