牛客竞赛34 能天使的愿望

发表于 分类于 阅读次数：

不是，出大问题，看我上一篇文章，刚写的分组背包，然后比赛就不会了?

好吧，其实比赛一眼就看出是分组背包了， 就是细节上不太会处理.

题目链接

题意

总共要买K个东西，告诉你了在每个商店买从1到M个商品的价格。但是每个商店只能有一种选择。问你买K个东西的最低价格。

思路

很显然的分组背包了。但是需要求的是最小值，不是最大值，因此我们初始化的时候需要设成inf，而不是0。 同时我们需要知道转移方程dp[j] = min(dp[j], dp[j - k] + $a[i][k]$) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
 
using namespace std;
typedef long long ll;
const int inf =0x3f3f3f3f;
ll a[806][805];
ll v[1005];
ll f[1005];
int main(){
   ll N, M, Y, K;
   cin >> N >> M >> K >> Y;
   for(int i = 1; i <= N; ++i){
       scanf("%lld",&v[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] += v[i] * j;
        }
    }
   }
    memset(f, inf, sizeof(f));
    f[0] = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = K; j >= 0; --j)
        {
            for(int k = 1; k <= M; ++k){
                f[j] = min(f[j], f[j - k] + a[i][k]);
            }
        }
    }
     cout << f[K] << '\n';
}