BZOJ 1017 魔兽地图DotR（树形DP）

心已赠人 2022-03-29 08:44 197阅读 0赞

题目链接：[http://61.187.179.132/JudgeOnline/problem.php?id=1017][http_61.187.179.132_JudgeOnline_problem.php_id_1017]

题意：有两类装备，高级装备A和基础装备B。现在有m的钱。每种B有一个单价和可以购买的数量上限。每个Ai可以由Ci种其他物品合成，给出Ci种其他物品每种需要的数量。每个装备有一个贡献值。求最大的贡献值。已知物品的合成路线是一个严格的树模型。即有一种物品不会合成其他任意物品，其余物品都会仅仅可用作合成另外一种物品。

思路：树形DP。 f\[i\]\[j\]\[k\]表示以第i种物品为根的子树花费j，向上层提供k个i所得到的的最大贡献值。

\#include <iostream>  
\#include <cstdio>  
\#include <string.h>  
\#include <algorithm>  
\#include <cmath>  
\#include <vector>  
\#include <queue>  
\#include <set>  
\#include <stack>  
\#include <string>  
\#include <map>  
\#include <time.h>  
  
  
\#define abs(x) ((x)>=0?(x):-(x))  
\#define i64 long long  
\#define u32 unsigned int  
\#define u64 unsigned long long  
\#define clr(x,y) memset(x,y,sizeof(x))  
\#define CLR(x) x.clear()  
\#define ph(x) push(x)  
\#define pb(x) push\_back(x)  
\#define Len(x) x.length()  
\#define SZ(x) x.size()  
\#define PI acos(-1.0)  
\#define sqr(x) ((x)\*(x))  
\#define MP(x,y) make\_pair(x,y)  
\#define EPS 1e-6  
  
  
\#define FOR0(i,x) for(i=0;i<x;i++)  
\#define FOR1(i,x) for(i=1;i<=x;i++)  
\#define FOR(i,a,b) for(i=a;i<=b;i++)  
\#define FORL0(i,a) for(i=a;i>=0;i--)  
\#define FORL1(i,a) for(i=a;i>=1;i--)  
\#define FORL(i,a,b)for(i=a;i>=b;i--)  
  
  
\#define rush() int CC;for(scanf("%d",&CC);CC--;)  
\#define Rush(n)  while(scanf("%d",&n)!=-1)  
using namespace std;  
  
  
void RD(int &x)\{scanf("%d",&x);\}  
void RD(i64 &x)\{scanf("%lld",&x);\}  
void RD(u64 &x)\{scanf("%I64u",&x);\}  
void RD(u32 &x)\{scanf("%u",&x);\}  
void RD(double &x)\{scanf("%lf",&x);\}  
void RD(int &x,int &y)\{scanf("%d%d",&x,&y);\}  
void RD(i64 &x,i64 &y)\{scanf("%lld%lld",&x,&y);\}  
void RD(u32 &x,u32 &y)\{scanf("%u%u",&x,&y);\}  
void RD(double &x,double &y)\{scanf("%lf%lf",&x,&y);\}  
void RD(double &x,double &y,double &z)\{scanf("%lf%lf%lf",&x,&y,&z);\}  
void RD(int &x,int &y,int &z)\{scanf("%d%d%d",&x,&y,&z);\}  
void RD(i64 &x,i64 &y,i64 &z)\{scanf("%lld%lld%lld",&x,&y,&z);\}  
void RD(u32 &x,u32 &y,u32 &z)\{scanf("%u%u%u",&x,&y,&z);\}  
void RD(char &x)\{x=getchar();\}  
void RD(char \*s)\{scanf("%s",s);\}  
void RD(string &s)\{cin>>s;\}  
  
  
void PR(int x) \{printf("%d\\n",x);\}  
void PR(int x,int y) \{printf("%d %d\\n",x,y);\}  
void PR(i64 x) \{printf("%lld\\n",x);\}  
void PR(i64 x,i64 y) \{printf("%lld %lld\\n",x,y);\}  
void PR(u32 x) \{printf("%u\\n",x);\}  
void PR(u64 x) \{printf("%llu\\n",x);\}  
void PR(double x) \{printf("%.2lf\\n",x);\}  
void PR(double x,double y) \{printf("%.5lf %.5lf\\n",x,y);\}  
void PR(char x) \{printf("%c\\n",x);\}  
void PR(char \*x) \{printf("%s\\n",x);\}  
void PR(string x) \{cout<<x<<endl;\}  
  
  
const int mod=10007;  
const i64 inf=((i64)1)<<40;  
const double dinf=1000000000000000000.0;  
const int INF=100000000;  
const int N=55;  
const int M=2005;  
  
  
  
  
int val\[N\],visit\[N\],n,m;  
int a\[N\],b\[N\];  
int c\[N\]\[N\],d\[N\]\[N\],num\[N\];  
int dp\[N\]\[M\],f\[N\]\[M\]\[N\*2\];  
  
  
  
  
  
  
void DFS(int x)  
\{   
    int i,j,k,t;  
    if(!num\[x\])  
    \{   
        b\[x\]=min(b\[x\],m/a\[x\]);  
        for(i=0;i<=b\[x\];i++)for(j=0;j<=i;j++)  
        \{   
            f\[x\]\[i\*a\[x\]\]\[j\]=val\[x\]\*(i-j);  
        \}  
        return;  
    \}  
    b\[x\]=INF;  
    for(i=1;i<=num\[x\];i++)  
    \{   
        k=c\[x\]\[i\];  
        DFS(k);  
        b\[x\]=min(b\[x\],b\[k\]/d\[x\]\[i\]);  
        a\[x\]+=d\[x\]\[i\]\*a\[k\];  
    \}  
    b\[x\]=min(b\[x\],m/a\[x\]);  
      
    for(t=0;t<=b\[x\];t++)  
    \{   
        clr(dp,-0x3f3f3f3f); dp\[0\]\[0\]=0;  
        for(i=1;i<=num\[x\];i++) for(j=0;j<=m;j++)  
        \{   
            for(k=0;k<=j;k++)   
            \{   
                dp\[i\]\[j\]=max(dp\[i\]\[j\],dp\[i-1\]\[j-k\]+f\[c\[x\]\[i\]\]\[k\]\[t\*d\[x\]\[i\]\]);  
            \}  
        \}  
        for(j=0;j<=m;j++) for(k=0;k<=t;k++)  
        \{   
            f\[x\]\[j\]\[k\]=max(f\[x\]\[j\]\[k\],dp\[num\[x\]\]\[j\]+val\[x\]\*(t-k));  
        \}  
    \}  
\}  
  
  
int main()  
\{   
    RD(n,m);  
    int i,j;  
    char s\[5\];  
    FOR1(i,n)  
    \{   
        RD(val\[i\]); RD(s);  
        if(s\[0\]=='A')  
        \{   
            RD(num\[i\]);  
            FOR1(j,num\[i\])  
            \{   
                RD(c\[i\]\[j\],d\[i\]\[j\]);  
                visit\[c\[i\]\[j\]\]=1;  
            \}  
        \}  
        else   
        \{   
            RD(a\[i\],b\[i\]);  
        \}  
    \}  
    FOR1(i,n) if(!visit\[i\]) break;  
    int root=i;  
    clr(f,-0x3f3f3f3f); DFS(root);  
    int ans=0;  
    for(i=0;i<=m;i++) for(j=0;j<=b\[root\];j++)  
    \{   
        ans=max(ans,f\[root\]\[i\]\[j\]);  
    \}  
    PR(ans);  
\}

[http_61.187.179.132_JudgeOnline_problem.php_id_1017]: http://61.187.179.132/JudgeOnline/problem.php?id=1017