NC14602. xinjun与阴阳师
描述
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
输入:
1 3 10 2 2 3 3 2 2 1 1 3 4 1 5 5
输出:
9
C++14(g++5.4) 解法, 执行用时: 128ms, 内存消耗: 284K, 提交时间: 2019-11-11 10:17:16
#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
int w[1010],v[1010],f[1010];
int main()
{
int t,n,m,a;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
memset(f,0,sizeof(f));
while(n--)
{
scanf("%d",&a);
for(int i=1;i<=a;i++)
scanf("%d",&v[i]);
for(int i=1;i<=a;i++)
scanf("%d",&w[i]);
for(int j=m;j>=0;j--)
for(int i=1;i<=a;i++)
{
if(j<w[i])continue;
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
printf("%d\n",f[m]);
}
}
C++(clang++ 11.0.1) 解法, 执行用时: 73ms, 内存消耗: 300K, 提交时间: 2022-08-17 09:55:10
#include<bits/stdc++.h>
using namespace std;
int c[1007],w[1007];
int main(){
int T;
cin>>T;
int d[1007];
for(int y=0;y<T;y++){
int N,M,s;
cin>>N>>M;
memset(d,0,sizeof(d));
for(int i=0;i<N;i++){
cin>>s;
for(int j=1;j<=s;j++)
cin>>c[j];
for(int j=1;j<=s;j++)
cin>>w[j];
for(int j=M;j>=0;j--){
for(int k=1;k<=s;k++)
if(j>=w[k])
d[j]=max(d[j],d[j-w[k]]+c[k]);
}
}
cout<<d[M]<<endl;
}
}