牛客-xinjun与阴阳师（分组背包）

牛客-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

思路：

分组背包，具体讲解可看：​​传送门​​代码： 不懂为什么res不能取-inf

#includeusing namespace std;const int maxn=1100;int dp[maxn][maxn];int a[maxn],v[maxn],w[maxn];int n,m;int main(){ int t;cin>>t; while(t--){ cin>>n>>m; int res=0; memset(dp,0,sizeof dp); for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++) dp[i][j]=dp[i-1][j]; int x;cin>>x; for(int j=1;j<=x;j++) cin>>v[j]; for(int j=1;j<=x;j++) cin>>w[j]; for(int j=1;j<=x;j++) for(int q=m;q>=w[j];q--){ dp[i][q]=max(dp[i][q],dp[i-1][q-w[j]]+v[j]); res=max(res,dp[i][q]); } } printf("%d\n",res); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。