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

题目描述

出题人寄给大家的一些闲话：参加了CSP-J/S 2019 的同学，考的都怎么样啊？不论是 500+ 收获省一而归的大佬，还是 100+ 无奈而回的小牛，无论你考的如何，是非成败转头空

不论是退役的前辈还是现役的"战友" ，只要你参与了这场比赛，就说明你对OI仍然抱有热爱，无论成绩如何，不变的，永远是那一颗热爱OI的心

好了，闲话扯了那么多，开始做题吧，希望这套题目能够带给你们愉快的做题体验

---------------窝是阔耐的分割线啦QAQ---------------

老板……不，义人，以手中的这把铳起誓，我将守护您的生命直到万物终结之日。

众所周知，能天使有两个愿望：

第一个愿望！请送我八把铳当礼物！我们天使都有自己的守护铳，但只有一把可不够看！
第二个愿望……找个人把我头上的这盏日光灯管关掉！

你显然不能帮能天使实现第二个愿望，但是你可以用你手上的龙门币帮她完成第一个愿望
在一条直线上均匀的分布着 N个店铺，每个店铺有 M 把铳出售，你不想自己出门买铳，所以打算网购（？）
在第 i 个店铺购买 j 把铳需要 Pi,j 元。如果在某商店购买了少于 Y 把铳，则每把铳需要额外支付 ai 元邮费，如果购买 Y 把及以上，则在这家店可以包邮。
另外，在每家店只能购买一次，也就是说你在每家店最多下一次订单
现在能天使想要 K 把铳，请问购买 K 把铳的最小花费是多少（总花费=总邮费+总购买费）？
当然，能天使并不喜欢铺张浪费，所以请不要购买超过 K 把铳，

输入描述:

 

第一行 3 个整数，N,M,K,Y

第二行 N 个整数，第 i 个数表示 ai

接下来 N 行，每行 M 个数，表示 Pi,j

输出描述:

一行一个非负整数，表示题目描述中的最小花费

示例1

输入

复制

5 8 10 3
10 20 100 5 1
1 3 5 7 9 11 13 15
2 4 6 8 10 12 14 16
1 2 3 4 5 6 7 8
1 3 6 10 15 21 28 36
10 20 30 40 50 60 70 80

输出

复制

12

说明

在样例1中，在第三家店买7把铳，然后在第一家买3把铳，总价为7+5=12，因为都是3把以上，所以不用邮费

示例2

输入

复制

5 8 10 8
10 20 100 5 1
1 3 5 7 9 11 13 15
2 4 6 8 10 12 14 16
1 2 3 4 5 6 7 8
1 3 6 10 15 21 28 36
10 20 30 40 50 60 70 80

输出

复制

21

说明

在样例2中，在第三家店买8把铳，然后在第四家店买2把，总价为8+3+2*5=21，其中2*5为在第四家店购买的邮费

备注:

 

N,M,K <= 800 ; K <= Min(800,N*M) ; Y<=K 

ai <= 100 Pi,j <= 10,000,000

Pi,j-1 <= Pi,j

 

分组背包是个啥？

 

我这人可能有毒

比赛时间19:00--22:00：

再看上星期一摸一样的场景（18:00结束）：

这就是命？？。

QAQ！

 

不会分组背包 改天来补

题意：

一共n个商店，每个商店有m把铳(chong四声)，一共要买k把，每个商店只能买一次，当买的数量少于y把铳时需要给每一把付运费。问买k把的最少花费

 

思路：

（纯手推版本 并不值得借鉴）

dp[i][j]表示从第i家商店交易完毕时共买了多少把（加上之前几个商店的）

第一维枚举商店1~n  第二维枚举此时的把数0~k   第三维枚举在第i个商店要买多少把0~m

状态转移方程：

dp[i][j]=max(dp[i-1][j-h]+a[i][h],dp[i][j])

a[i][h]即在第i个商店买h把的钱数

从第i个商店买完一共买了j把了，所以dp[i-1][j-h]表示在第i个商店之前买了j-h把的钱数

 

至于运费什么的 提前预处理

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
ll a[N][N],b[N];
ll dp[N][N];

int main()
{
    int n,m,k,y;
    while(~scanf("%d%d%d%d",&n,&m,&k,&y))
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            scanf("%lld",&b[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%lld",&a[i][j]);
                if(j<y)
                    a[i][j]+=b[i]*j;
            }
        }
        for(int i=1;i<=m;i++)
            dp[1][i]=a[1][i];
        for(int i=2;i<=n;i++)    ///商店
        {
            for(int j=0;j<=k;j++)    ///总把数
            {
                ll tmp=inf;
                bool flag=0;
                for(int h=min(j,m);h>=0;h--)    ///从多到少枚举第i家商店能买的数量，那么第i家商店之前的把数是从少到多.注意左边界 取总把数 和 该店最多能买的把数 的最小值.
                {
                    if(dp[i-1][j-h]<=0&&j-h>0)    ///(逆序枚举的用途)如果为0，说明上一家店不能买这么多 后面更多肯定都不行
                        break;
                    tmp=min(dp[i-1][j-h]+a[i][h],tmp);
                    flag=1;    ///防止把inf赋给dp[i][j] 这样写比较蠢
                }
                if(flag)
                    dp[i][j]=tmp;
            }
        }
        cout<<dp[n][k]<<'\n';///n个商店 总共k把
    }
    return 0;
}