嘉兴网站建设维护,宿迁seo公司,价格优惠,互助盘网站开发来源#xff1a;牛客网#xff1a; 文章目录购物题目描述题解#xff1a;代码#xff1a;购物
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
64bit IO Format: %lld题目描述 在遥远的东方#xff0c;有…来源牛客网 文章目录购物题目描述题解代码购物
时间限制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行到第n1行每行m个正整数第x1行的第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。
题解
根据题意我们一天最少吃一个那我们只需要买n个就行 dp[i][j]表示第i天总共买j个糖果的最低价格 枚举第i天买了多少糖果 dp[i][j]min(dp[i-1][j-k]sum[i][k](k)*(k)) (k从0到j枚举) 前i-1天买了j-k个糖果第i天就买k个糖果
代码
#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 i1;in;i){for(int j1;jm;j)cina[i][j];sort(a[i]1,a[i]1m);for(int j1;jm;j)sum[i][j]sum[i][j-1]a[i][j];}f[0][0]0;for(int i1;in;i)for(int ji;jn;j)for(int k0;kjkm;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);coutf[n][n]endl;return 0;
}