题解 P1860 【新魔法药水】

· · 题解

这题有点难想啊，看了一个小时才有思路，也许是我太弱了

首先，这道题肯定是DP。

其次，分析样例，会发现题目有个隐藏条件：只能用开局的V元钱买入药品。

经过对题面的研究，我们可以发现，那一长串药物合成关系实在不好在DP中用上，我们应当把他们变得易于处理，如用ans[i][j]表示第i个物品在用j次魔法的前提下所需最小代价（即原材料价钱）。

但ans[i][j]不太好直接求，我们可以再开一个DP数组ant[i][j]表示前i个药品在使用j次魔法前提下合成所需最小代价。这样就能通过ant[i][j]将合成原材料和合成品联系起来，顾及到 需要魔法总次数 等诸多因素。

有了以上作为基础，DP处理出结果就方便多了。设DP[i][j]为使用第i次魔法，使用j块钱所获最大利润，依此列式即可。

还有，一种药品可能有多种合成方式。我因把药品与合成关系一一对应WA了一版。

#include<bits/stdc++.h>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=300;
int m,n,q,k,s[N],h[N],op,ans[N][N],dp[N][1005],ant[N][50];
struct line
{
  int a,l,p[N];
}e[N];
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=gi();q=gi();k=gi();
  fp(i,1,n) s[i]=gi(),h[i]=gi();
  fp(i,1,m)
    {
      e[i].a=gi();e[i].l=gi();
      fp(j,1,e[i].l) e[i].p[j]=gi();
    }
  fp(i,1,n) fp(j,0,k) ans[i][j]=s[i];
  fp(o,1,k)
    fp(i,1,m)
      {
        fp(j,1,e[i].l)//枚举一合成关系中的物品
      {
        fp(t,0,o-1)//总魔法次数
          {
        ant[j][t]=1e9;
        fp(tt,0,t)//当前物品使用魔法次数 
        ant[j][t]=min(ant[j][t],ant[j-1][t-tt]+ans[e[i].p[j]][tt]);
          }
      }
    ans[e[i].a][o]=min(ans[e[i].a][o],ant[e[i].l][o-1]);
      }//处理药品合成信息
  fp(i,1,n)
    fp(j,0,k)
    fp(t,0,k-j)//枚举当前物品使用魔法次数
    fp(s,0,q-ans[i][j])//枚举使用钱数
    dp[j+t][s+ans[i][j]]=max(dp[j+t][s+ans[i][j]],dp[t][s]+h[i]-ans[i][j]);//简单DP求解
  printf("%d\n",dp[k][q]);
  return 0;
}