A4382. 【算法】大赢家Gold King2
编程题
入门
知识点
题目描述
Gold King一招得手，心情荡漾的不得了，于是开始再接再厉，背着容量为x的背包瞄准了华盛顿的美联储去抢钱。美联储不比其他银行，里面的钱又多又杂，存放着n(0 <=n <=800)种面额的货币，而且每种货币的数量为m，每个对应货币的体积为v，该体积下价值为c都不同。求Gold King这次最多能偷走多少价值的东西，成为大大大大赢家？
输入格式
第一行输入两个整数n和x，分别表示n种货币和背包容量为x，
第二行输入n种货币的体积v，
第三行输入n种货币的价值c，
第四行输入n种货币的数量m。
第二行输入n种货币的体积v，
第三行输入n种货币的价值c，
第四行输入n种货币的数量m。
输出格式
输出对应Gold King能偷走的最多的价值。
输入输出样例
输入 #1
5 20 10 5 7 3 6 6 9 2 5 7 5 3 9 2 1
输出 #1
32
说明/提示
1 <=x <=1200
1 <=v <=500
1 <=c <=500
1 <=m <=500
“有二进制优化和单调队列优化，有想法可以试着去尝试一下”
1 <=v <=500
1 <=c <=500
1 <=m <=500
“有二进制优化和单调队列优化，有想法可以试着去尝试一下”