DP

首先考慮如何將答案DP轉(zhuǎn)移出來(lái)

記$dp[i][j]$表示使用了$i$次魔法，用了$j$個(gè)金幣時(shí)的最大獲利

因?yàn)榭梢詫讉€(gè)藥水合成一個(gè)藥水

那么在轉(zhuǎn)移時(shí)會(huì)發(fā)現(xiàn)還需要處理出用了第$i$種藥水由$j$次魔法合成的最小成本，記此為$tc[i][j]$

那么轉(zhuǎn)移方程就是$dp[i][j]=min(dp[i-q][j-tc[p][q]]+w[p]-tc[p][q])$

$w$表示這個(gè)藥水的售價(jià)

那么現(xiàn)在就要處理出$tc$數(shù)組

對(duì)于$tc[i][j]$，因?yàn)楫?dāng)前合成i需要一次操作，那么分配給其原料的合成次數(shù)為$j-1$

$tc[i][j]=max(\sum_{k=1}^{Number}tc[a[k]][t[k]])$

且$\sum_{k}^{Number}t[k]=j-1$

$a$數(shù)組表示這個(gè)合成這個(gè)藥水的原料，$t$為給這個(gè)原料分配合成的次數(shù)，$Number$為原料總數(shù)

那么這個(gè)表達(dá)式也是可以DP轉(zhuǎn)移的

記$tmp[i][j]$表示前$i$個(gè)原料，用了$j$次魔法的最小成本

填表轉(zhuǎn)移即可

注意此處合成同一個(gè)藥水的配方可能有多個(gè)

那么在這多個(gè)配方中$tc$選取最佳的即可

#include <bits/stdc++.h> #define inf (int)1e9 using namespace std; int n,m,v,k,tmp[100][100],tc[100][100]; int dp[45][1100]; struct node {int v,w; }sh[100]; struct magic {int p,h;vector <int> a; }d[300]; int main() {scanf("%d%d%d%d",&n,&m,&v,&k);for (int i=1;i<=n;i++)scanf("%d%d",&sh[i].v,&sh[i].w);for (int i=1;i<=m;i++){scanf("%d%d",&d[i].p,&d[i].h);for (int j=1;j<=d[i].h;j++){int num;scanf("%d",&num);d[i].a.push_back(num);}}for (int i=1;i<=n;i++){for (int j=1;j<=k;j++)tc[i][j]=inf;tc[i][0]=sh[i].v;}for (int j=1;j<=k;j++){for (int i=1;i<=m;i++){for (int p=0;p<j;p++)tmp[0][p]=tc[d[i].a[0]][p];//初始值for (int p=1;p<(int)d[i].a.size();p++){for (int q=0;q<j;q++){tmp[p][q]=inf;for (int r=0;r<=q;r++)tmp[p][q]=min(tmp[p][q],tmp[p-1][r]+tc[d[i].a[p]][q-r]);//tmp的DP轉(zhuǎn)移}}tc[d[i].p][j]=min(tc[d[i].p][j],tmp[(int)d[i].a.size()-1][j-1]);//在多個(gè)方案中取最優(yōu)}}for (int i=0;i<=k;i++){for (int j=0;j<=v;j++)dp[i][j]=-inf;}dp[0][0]=0;for (int i=0;i<=k;i++){for (int j=0;j<=v;j++){for (int p=1;p<=n;p++){for (int q=0;q<=i;q++){if (tc[p][q]==inf)continue;if (j>=tc[p][q])//注意邊界條件dp[i][j]=max(dp[i][j],dp[i-q][j-tc[p][q]]+sh[p].w-tc[p][q]); //轉(zhuǎn)移}}}}int ans=0;for (int i=0;i<=k;i++){for (int j=0;j<=v;j++)ans=max(ans,dp[i][j]);//統(tǒng)計(jì)答案}printf("%d\n",ans); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/huangchenyan/p/11305070.html

總結(jié)

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

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