洛谷P5365 [SNOI2017] 英雄联盟 题解

题目链接：P5365 [SNOI2017] 英雄联盟

题意：正在上大学的小皮球热爱英雄联盟这款游戏，而且打的很菜，被网友们戏称为「小学生」。

现在，小皮球终于受不了网友们的嘲讽，决定变强了，他变强的方法就是：买皮肤！

小皮球只会玩 $\text{N}$ 个英雄，因此，他也只准备给这 $\text{N}$ 个英雄买皮肤，并且决定，以后只玩有皮肤的英雄。

这 $\text{N}$ 个英雄中，第 $\text{i}$ 个英雄有 $K_i$ 款皮肤，价格是每款 $C_i$ Q 币（同一个英雄的皮肤价格相同）。

为了让自己看起来高大上一些，小皮球决定给同学们展示一下自己的皮肤，展示的思路是这样的：对于有皮肤的每一个英雄，随便选一个皮肤给同学看。

比如，小皮球共有 5 个英雄，这 5 个英雄分别有 $\text{0,0,3,2,4}$ 款皮肤，那么，小皮球就有 $3 \times 2 \times 4 = 24$ 种展示的策略。

现在，小皮球希望自己的展示策略能够至少达到 $\text{M}$ 种，请问，小皮球至少要花多少钱呢？

题目要求的就是数量要超过 $m$ ，并要求价格最少

如果直接dp会带上一些乘法除法的转移，不太好

考虑转化问题，求出每种价格可以获得的最多的数量

那么这就变成了一个类似于多重背包的dp问题

其中价格是费用，即 $w[i]$

状态转移方程：

$$dp[j]=\max_{0 \le k \le \min\left(v[i],\left\lfloor\frac{j}{w[i]}\right\rfloor\right)}(dp[j],dp[j-k\times w[i]]\times k)$$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(205)
#define M (int)(3e5+15)
int n,m,sum;
int w[N],v[N],dp[M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> v[i];
    for(int i=1; i<=n; i++)
    {
        cin >> w[i];
        sum+=w[i]*v[i];
    }
    dp[0]=1;
    for(int i=1; i<=n; i++)
        for(int j=sum; j>=0; j--)
            for(int k=1; k*w[i]<=j&&k<=v[i]; k++)
                dp[j]=max(dp[j],dp[j-k*w[i]]*k);
    int mn=INF;
    for(int i=1; i<=sum; i++)
        if(dp[i]>m){cout << i;return 0;}
    
    return 0;
}