[关闭]
@ysner 2018-10-17T14:28:24.000000Z 字数 1787 阅读 2053

[JSOI2008]魔兽地图

DP 树形DP 背包


题面

戳我

解析

感觉这道题是一道限制比较多的树形背包。

可以想见,所有装备之间的关系(合成就相当于树上指向)构成了森林。

然后对于合成关系,我们必须要考虑该装备有多少个用于合成其它装备,这样才能统计出该种装备实际贡献了多少力量值。

那么就设表示第种装备,向上贡献了个,实际合成花了元,其体系内装备所贡献的最大力量值。

各基本装备直接预处理
对于高级装备,先枚举合成了个,然后再枚举在各儿子中各花了多少钱转移(它们的必须是合成个该装备要求的个数),这样才能背包处理出合成该装备所需的钱。
接下来就可以预处理高级装备的了。

最后还要对各棵树顶端的装备进行背包

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define mk make_pair
  12. #define pb push_back
  13. #define fi first
  14. #define se second
  15. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  16. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  17. using namespace std;
  18. const int N=52,M=2002;
  19. int n,m,val[N],cost[N],lim[N],dp[M],f[N][N*2][M],g[M];
  20. char op[5];
  21. bool Base[N];
  22. vector<pair<int,int> >E[N];
  23. il int gi()
  24. {
  25. re int x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void dfs(re int u)
  33. {
  34. re int sz=E[u].size();
  35. if(!sz)
  36. {
  37. lim[u]=min(lim[u],m/cost[u]);
  38. fp(i,0,lim[u])
  39. fp(j,0,i)
  40. f[u][j][i*cost[u]]=val[u]*(i-j);
  41. return;
  42. }
  43. lim[u]=1e9;
  44. fp(i,0,sz-1)
  45. {
  46. re int v=E[u][i].fi,w=E[u][i].se;
  47. dfs(v);
  48. cost[u]+=cost[v]*w;lim[u]=min(lim[u],lim[v]/w);
  49. }
  50. lim[u]=min(lim[u],m/cost[u]);
  51. fp(i,0,lim[u])
  52. {
  53. memset(g,-63,sizeof(g));g[0]=0;
  54. fp(j,0,sz-1)
  55. {
  56. re int v=E[u][j].fi,w=E[u][j].se,tmp;
  57. fq(k,m,0)
  58. {
  59. tmp=-1e9;
  60. fp(l,0,k) tmp=max(tmp,g[l]+f[v][i*w][k-l]);
  61. g[k]=tmp;
  62. }
  63. }
  64. fp(j,0,i)
  65. fp(k,0,m)
  66. f[u][j][k]=max(f[u][j][k],g[k]+val[u]*(i-j));
  67. }
  68. }
  69. int main()
  70. {
  71. n=gi();m=gi();
  72. fp(i,1,n)
  73. {
  74. val[i]=gi();
  75. scanf("%s",op);
  76. if(op[0]=='A')
  77. {
  78. re int c=gi(),x,y;
  79. fp(j,1,c) x=gi(),y=gi(),Base[x]=1,E[i].pb(mk(x,y));
  80. }
  81. if(op[0]=='B') cost[i]=gi(),lim[i]=gi();
  82. }
  83. memset(f,-63,sizeof(f));
  84. fp(i,1,n)
  85. if(!Base[i])
  86. {
  87. dfs(i);
  88. fq(j,m,0)
  89. fp(k,0,j)
  90. dp[j]=max(dp[j],dp[j-k]+f[i][0][k]);
  91. }
  92. printf("%d\n",dp[m]);
  93. return 0;
  94. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注