題目描述

商店里有N種藥水，每種藥水都有一個(gè)售價(jià)和回收價(jià)。小S攢了V元錢(qián)，還會(huì)M種魔法，可以把一些藥水合成另一種藥水。他一天可以使用K次魔法，問(wèn)他一天最多賺多少錢(qián)？

輸入輸出格式

輸入格式：

第一行四個(gè)數(shù)N、M、V、K

接下來(lái)N行，每行兩個(gè)數(shù)，表示藥水的售價(jià)和回收價(jià)。

接下來(lái)M行，每行若干個(gè)數(shù)，第一個(gè)數(shù)表示魔法的成品，第二個(gè)數(shù)是原料的種數(shù)，接下來(lái)為各種原料的編號(hào)

輸出格式：

一個(gè)數(shù)，表示小S的最大利潤(rùn)

輸入輸出樣例

輸入樣例#1：

4 2 6 3
1 0
1 0
5 3
20 15
3 2 1 2
4 3 1 2 3

輸出樣例#1：

12

說(shuō)明

N<=60 M<=240

V<=1000

k<=30

---

就是個(gè)背包,但是挺麻煩的

跟昊哥一塊搞的

先預(yù)處理出(v[i][j])表示使用j次魔法后變成第i個(gè)物品的花費(fèi)

這可以用分層 + 背包來(lái)做

就是一層一層的更新

求出 v 數(shù)組以后直接簡(jiǎn)單背包一下就好辣

#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個(gè)物品使用j次魔法的花費(fèi) 
    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 ;
}

總結(jié)

以上是生活随笔為你收集整理的新魔法药水的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。