xinjun与阴阳师

题目

xinjun是各类手游的狂热粉丝，因随手一氪、一氪上千而威震工大，现在他迷上了阴阳师。xinjun玩手游有一个习惯，就是经过层层计算制定出一套方案来使操作利益最大化(因此即使有扫荡券也不用，故称圣雄肝帝)。已知阴阳师有N个模式可以操作，模式i有ai种操作，但每种模式每日只能选用一种操作，可以不选。操作j能收益vj，但需要花费体力wj点。xinjun每日拥有体力M点，求他每日最多能得到多少收益。

链接

https://ac.nowcoder.com/acm/contest/18495/H

考察点

该题目为背包dp；

是一个很简单且很经典的背包dp；

在做dp类问题时一定要感受从点到面的变化，那种感觉老爽了；

背包问题一般模拟的都是在一定值内获得的最多/最少的东西；

还会经常出现经典的三重循环；

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
    ll f[1005];//背包即是体力
    ll n,m,w[1005][1005],v[1005][1005],i,j,a[1005],k;
    ll t;
    cin>>t;
    while(t--)
    {
        for(i=0;i<1005;i++)
            f[i]=0;
        cin>>n>>m;
        for(ll i=0;i<n;i++)
        {
            cin>>a[i];
            for(j=0;j<a[i];j++) 
                cin>>v[i][j];
            for(j=0;j<a[i];j++)
                cin>>w[i][j];
        }
        for(ll p=0;p<n;p++)       //进行遍历、dp
            for(i=m;i>0;i--)        //从血量多带到血量少遍历
                for(j=0;j<a[p];j++)    //对不同方案进行遍历
                {
                    if(i-w[p][j]>=0)
                     f[i]=max(f[i],f[i-w[p][j]]+v[p][j]);//记录该体力最优值
                }

        cout<<f[m]<<endl;
    }
}