傳送門：QAQQAQ

?

題意：商店里有N種藥水，每種藥水都有一個售價和回收價。小S攢了V元錢，還會M種魔法，可以把一些藥水合成另一種藥水。他一天可以使用K次魔法，問他一天最多賺多少錢？

N<=60 M<=240

V<=1000

k<=30

?

思路：這是一道比較有技術含量的DP題。

我們定義$dp[i][j]$為消耗了$i$個金幣（金幣不能回收），使用了$j$次魔法能得到的最多錢（最后求答案時注意要$dp[i][j]-i$）

在直接轉移的過程中，我們無法知道使用的金幣都花在了哪些藥品上，各種魔法又都用了幾次，直接枚舉又不知如何下手，所以我們要定義輔助數組：

我們定義$cost[i][j]$為最終消耗了$j$次魔法，得到了藥品$i$的最小花費，這樣轉移方程就很容易了：
$dp[i][j]=max(dp[i-cost[p][t]][j-t]+w[p])$

?

$cost[i][j]=min(\sum cost[magic[p].to[t]][r]) (\sum r=j-1)$

而在處理$cost[i][j]$時我們又遇到了一些難題：我們沒法知道在得到$i$的魔法中每種原料到底用了幾次，其“下層”的魔法各用了幾次，所以我們要再開一個輔助數組

?

我們定義對于當前搜到的魔法$i$，$ant[t][r]$為前該魔法前$t$個物品使用了$r$次魔法的最小花費

我們可以通過$t$逐步增大來更新后面的$ant$，其中$cost$和$ant$數組是互相利用的。

（在代碼實現方面，要注意$init$函數里的循環順序，一定要先枚舉使用魔法數，這樣才能保證在當前枚舉到魔法數$j$時前面所有比$j$小的$ant$,$cost$數組已經最優化，這樣就可以無憂無慮地轉移啦~~）

?

代碼：（用刷表寫的，之前刷表越界了。。。）

#include<bits/stdc++.h> using namespace std; const int inf=(int)1e9;int cost[300][300],dp[1020][300],ant[301][50]; int n,m,v,k; int b[10001],s[10001]; struct node{int from,len;int to[101]; }E[250];void checkmax(int &x,int y) {if(x<y) x=y; }void checkmin(int &x,int y) {if(x>y) x=y; }void init() {for(int i=1;i<=n;i++){for(int j=0;j<=k;j++) cost[i][j]=b[i];}for(int j=1;j<=k;j++){for(int i=1;i<=m;i++){for(int t=1;t<=E[i].len;t++){for(int r=0;r<=j-1;r++){ant[t][r]=inf;for(int p=0;p<=r;p++) checkmin(ant[t][r],ant[t-1][p]+cost[E[i].to[t]][r-p]);}}checkmin(cost[E[i].from][j],ant[E[i].len][j-1]);}} }void solve() {memset(dp,0,sizeof(dp));for(int i=0;i<=v;i++){for(int j=0;j<=k;j++){for(int t=1;t<=n;t++)//新加藥水種類 {for(int p=0;p<=k-j;p++)//新用魔法次數 {if(i+cost[t][p]>v||j+p>k) continue;checkmax(dp[i+cost[t][p]][j+p],dp[i][j]+s[t]);}}}}int ans=0;for(int i=0;i<=v;i++){for(int j=0;j<=k;j++) checkmax(ans,dp[i][j]-i);}cout<<ans<<endl; }int main() {scanf("%d%d%d%d",&n,&m,&v,&k);for(int i=1;i<=n;i++) scanf("%d%d",&b[i],&s[i]);for(int i=1;i<=m;i++){scanf("%d",&E[i].from);scanf("%d",&E[i].len);for(int j=1;j<=E[i].len;j++) scanf("%d",&E[i].to[j]);}init();solve();return 0; } View Code

?

轉載于:https://www.cnblogs.com/Forever-666/p/11306264.html

總結

以上是生活随笔為你收集整理的洛谷P1860——新魔法药水的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。