购物
题目描述 :
在遥远的东方，有一家糖果专卖店。 这家糖果店将会在每天出售一些糖果，它每天都会生产出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[i][j]表示前i天买j个糖果的最小代价，那么枚举第i+1天买的糖果数量即有转移 dp[i+1][j+k]=min(dp[i+1][j+k],dp[i][j]+k2+c[i+1][k]),j≥i,j+k≥i+1
其中c[i][j] 表示在第i天买j个糖果所需的最小代价，dp[n][n]即为答案，时间复杂度O(n3)
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int a[550][550];
ll sum[550][550],f[550][550],n,m;
int main(){
memset(f,0x3f,sizeof f);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cin>>a[i][j];
sort(a[i]+1,a[i]+1+m);
for(int j=1;j<=m;j++)
sum[i][j]=sum[i][j-1]+a[i][j];//记录每天前j件的糖的最少话费。
}
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)//因为前i天至少需要i颗糖，所以j从 == i开始循环到n。
for(int k=0;k<=j&&k<=m;k++)
if(f[i-1][j-k]!=0x3f3f3f3f)
f[i][j]=min(f[i][j],f[i-1][j-k]+sum[i][k]+k*k);
cout<<f[n][n]<<endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读