题目描述
商店里有N种药水，每种药水都有一个售价和回收价。小S攒了V元钱，还会M种魔法，可以把一些药水合成另一种药水。他一天可以使用K次魔法，问他一天最多赚多少钱？
输入输出格式
输入格式：
第一行四个数N、M、V、K
接下来N行，每行两个数，表示药水的售价和回收价。
接下来M行，每行若干个数，第一个数表示魔法的成品，第二个数是原料的种数，接下来为各种原料的编号
输出格式：
一个数，表示小S的最大利润
输入输出样例
输入样例#1：
4 2 6 3
1 0
1 0
5 3
20 15
3 2 1 2
4 3 1 2 3
输出样例#1：
12
说明
N<=60 M<=240
V<=1000
k<=30
就是个背包,但是挺麻烦的
跟昊哥一块搞的
先预处理出(v[i][j])表示使用j次魔法后变成第i个物品的花费
这可以用分层 + 背包来做
就是一层一层的更新
求出 v 数组以后直接简单背包一下就好辣
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 245 ;
const int N = 1005 ;
const int INF = 1e9 + 7 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m , W , tot ;
int val[M] , cost[M] ;
int v[M][M] , res[M] ;
int temp[M][M] ;
vector < int > p[M] ;
int f[N][M >> 2] ;
inline void Update(int t , int m) {
memset(temp , 63 , sizeof(temp)) ;
temp[0][0] = 0 ;
for(int i = 0 ; i <= m ; i ++)
for(int j = 1 , u ; j < p[t].size() ; j ++) {
u = p[t][j] ;
for(int k = 0 ; k <= i ; k ++) {
temp[j][i] = min(temp[j][i] , temp[j - 1][i - k] + v[u][k]) ;
}
}
v[res[t]][m + 1] = min( v[res[t]][m + 1] , temp[p[t].size() - 1][m] ) ;
for(int i = m + 1 ; i <= tot ; i ++)
v[res[t]][i] = min(v[res[t]][i] , v[res[t]][m + 1]) ;
}
int main() {
n = read() ; m = read() ; W = read() ; tot = read() ;
for(int i = 1 ; i <= n ; i ++) {
val[i] = read() ;
cost[i] = read() ;
for(int j = 0 ; j <= tot ; j ++)
v[i][j] = val[i] ;
}
for(int i = 1 , x , Num ; i <= m ; i ++) {
res[i] = read() ; Num = read() ;
p[i].push_back(0) ;
while(Num -- ) {
x = read() ;
p[i].push_back(x) ;
}
}
for(int i = 1 ; i <= tot ; i ++) // i表示使用i次魔法
for(int j = 1 ; j <= m ; j ++) // 第j种魔法
Update(j , i - 1) ;
// f[i][j] 表示花i元使用j次魔法的收益
// v[i][j] 表示第i个物品使用j次魔法的花费
for(int i = 1 ; i <= W ; i ++)
for(int j = 0 ; j <= tot ; j ++)
for(int k = 1 ; k <= n ; k ++)
for(int l = 0 ; l <= j ; l ++)
if(i - v[k][l] >= 0)
f[i][j] = max(f[i][j] , f[i - v[k][l]][j - l] + (cost[k] - v[k][l]) ) ;
cout << f[W][tot] << endl ;
return 0 ;
}