xinjun与阴阳师_牛客博客

@[toc]

题目描述

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

输入描述:

第一行一个正整数T(T<=10)，表示共有T组数据。

对于每组数据，第一行两个正整数N，M(1<=N，M<=1000)。

接下来N段数据，每段第一行一个正整数ai(1<=ai<=1000)，第二行ai个正整数vj(1<=vj<=1000)，第三行ai个正整数wj(1<=wj<=1000)。

每组数据ai之和不大于104。

输出描述:

对每组数据输出一行，即xinjun每日最多能得到多少收益。

示例1
输入

输出

题解：

01背包，但是独特点在于，N个模式，每个模式有ai种操作，一个模式只能用一次操作，也就是并非所有操作都参与最终受益，相同模式下只能选一个操作。
这怎么解决呢？
我们用二维数字来存受益与花费
v[i][j]表示第i个模式下第j种操作的受益
w[i][j]表示第i个模式下第j种操作的花费
那么递推方程就是
f[j] = max(f[j],f[j-w[i][k]]+v[i][k]);
三重for循环的含义
在当前容量下，枚举每一种操作，保留最佳情况
我原本以为复杂度会超，发现我想太多了，数据有点水。。
这种方法应该是算是比较简单明了

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1005;
int n,m;
int f[maxn];
int c[maxn];
int w[maxn][maxn];
int v[maxn][maxn];
int t;

int main()
{
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1; i <= n; ++i)
        {
            cin >> c[i];
            for(int j = 1; j <= c[i]; ++j)
            {
                cin >> v[i][j];
            }
            for(int j = 1; j <= c[i]; ++j)
            {
                cin >> w[i][j];
            }
        }
        memset(f,0,sizeof(f));
        f[0] = 0;
        for(int i = 1; i <= n; ++i)//模式 
        {
            for(int j = m; j >= 0; --j)
            {
                for(int k = 1; k <= c[i]; ++k)//第i种操作 
                {
                    if(j>=w[i][k])
                        f[j] = max(f[j],f[j-w[i][k]]+v[i][k]);
                }
            }
        }

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

还有个方式：
参考
模式与模式之间都是独立的
每一个模式不是只能选一种吗？那我就挑选出最佳的操作，然后进入下一个模式，一直这样走

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
struct node{
    int f;
    int ne;
}dp[N];

int main (){
    int T;
    cin>>T;
    while(T--){
        int P,W;
        scanf("%d %d",&P,&W);
        while(P--){
            int n;
            scanf("%d",&n);
            int w[n],v[n];
            for(int i=0;i<n;i++){
                scanf("%d",&v[i]);
            }
            for(int i=0;i<n;i++){
                scanf("%d",&w[i]);
            }

            for(int i=0;i<n;i++){
                for(int j=W;j>=w[i];j--){
                    dp[j].ne=max(dp[j].ne,dp[j-w[i]].f+v[i]);

                }
            }
            for(int i=0;i<=W;i++){
                dp[i].f=dp[i].ne;
            }
        }

        cout<<dp[W].f<<endl;
        memset(dp,0,sizeof dp);
    }
    return 0;
}