购物

题目描述 :

在遥远的东方,有一家糖果专卖店。 这家糖果店将会在每天出售一些糖果,它每天都会生产出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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • AtCoder Beginner Contest 154

    思路:这个题不是很难,但是我一上去就想要用map,然后就很悲催,map里面人家按照键值给你排序,所以输出的时候会有错!

    用户7727433
  • 2017 年ICPC 中国大陆区域赛铜牌题解

    题意:有n只猫m条鱼,然后每只猫吃鱼的速度不同,为ci,,,然后吃完当前鱼可以继续吃下一条,问经过x分钟后还剩下几只完整的鱼几只不完整的鱼。

    用户7727433
  • 牛客小白月赛22 A~~J

    A.链接:https://ac.nowcoder.com/acm/contest/4462/A 来源:牛客网

    用户7727433
  • 每日算法系列【LeetCode 1039】多边形三角剖分的最低得分

    给定 N,想象一个凸 N 边多边形,其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。

    godweiyang
  • 使用WPF教你一步一步实现连连看(一)

    第一步:   问题,怎样动态的建立一个10*10的grid(布局) 第二步:   问题,怎样将button放到上边那个布局中(这个是我查资料才知道的,一般都是用...

    hbbliyong
  • 【POJ 1001】Exponentiation (高精度乘法+快速幂)

    将R用字符串读进来,找到小数点的位置,然后转为整数。 用高精度乘法和快速幂计算。输出时要确定一下小数点的位置。

    饶文津
  • 洛谷P3746 [六省联考2017]组合数问题

    题目描述 组合数 C_n^mCnm​ 表示的是从 n 个互不相同的物品中选出 m 个物品的方案数。举个例子,从 (1;2;3) 三个物品中选择两个物品可以有 (...

    attack
  • Android AIDL实现跨进程通信的示例代码

    AIDL是Android接口定义语言,它可以用于让某个Service与多个应用程序组件之间进行跨进程通信,从而可以实现多个应用程序共享同一个Service的功能...

    砸漏
  • java中循环小Demo练习分享

    很多同学在学习java循环过程中找不到好的练习例子,这里给大家分享一下学习java循环时常用的例子!

    柠檬Lem
  • 团体程序设计天梯赛-练习集 L1-017 到底有多二

    一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值。如果这个数是负数,则程度增加0.5倍;如果还是个偶数,则再增加1倍。例如数字 -13142223...

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券