3d建模网站,厦门市建设局思明建设分局官方网站,免费开网店免费供货,高明网站设计公司来源#xff1a;牛客网 文章目录题目描述题解#xff1a;代码#xff1a;题目描述 xinjun是各类手游的狂热粉丝#xff0c;因随手一氪、一氪上千而威震工大#xff0c;现在他迷上了阴阳师。xinjun玩手游有一个习惯#xff0c;就是经过层层计算制定出一套方案来使操作利益…来源牛客网 文章目录题目描述题解代码题目描述 xinjun是各类手游的狂热粉丝因随手一氪、一氪上千而威震工大现在他迷上了阴阳师。xinjun玩手游有一个习惯就是经过层层计算制定出一套方案来使操作利益最大化(因此即使有扫荡券也不用故称圣雄肝帝)。已知阴阳师有N个模式可以操作模式i有ai种操作但每种模式每日只能选用一种操作可以不选。操作j能收益vj但需要花费体力wj点。xinjun每日拥有体力M点求他每日最多能得到多少收益。 输入描述: 第一行一个正整数T(T10)表示共有T组数据。 对于每组数据第一行两个正整数NM(1NM1000)。 接下来N段数据每段第一行一个正整数ai(1ai1000)第二行ai个正整数vj(1vj1000)第三行ai个正整数wj(1wj1000)。 每组数据ai之和不大于104。 输出描述: 对每组数据输出一行即xinjun每日最多能得到多少收益。 示例1 输入
1
3 10
2
2 3
3 2
2
1 1
3 4
1
5
5输出
9题解
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循环的含义 在当前容量下枚举每一种操作保留最佳情况 我原本以为复杂度会超发现我想太多了数据有点水。。 这种方法应该是算是比较简单明了
代码
#includebits/stdc.husing 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(jw[i][k])f[j] max(f[j],f[j-w[i][k]]v[i][k]);}}}cout f[m] endl;}return 0;
}还有个方式 参考 模式与模式之间都是独立的 每一个模式不是只能选一种吗那我就挑选出最佳的操作然后进入下一个模式一直这样走
#includeiostream
#includecstring
using namespace std;
const int N 1010;
struct node{int f;int ne;
}dp[N];int main (){int T;cinT;while(T--){int P,W;scanf(%d %d,P,W);while(P--){int n;scanf(%d,n);int w[n],v[n];for(int i0;in;i){scanf(%d,v[i]);}for(int i0;in;i){scanf(%d,w[i]);}for(int i0;in;i){for(int jW;jw[i];j--){dp[j].nemax(dp[j].ne,dp[j-w[i]].fv[i]);}}for(int i0;iW;i){dp[i].fdp[i].ne;}}coutdp[W].fendl;memset(dp,0,sizeof dp);}return 0;
}
