bzoj 1017: [JSOI2008]魔兽地图DotR

/**************************************************************    Problem: 1017    User: lxy8584099    Language: C++    Result: Accepted    Time:8176 ms    Memory:59680 kb****************************************************************/ /*    P[] 表示力量  L[]表示数量上限 M[]表示花费     每个装备建一个树 然后和在一个节点上    f[i][j][k] 表示第i个装备 j个用于合成另一个装备 花费了k元 所得的最大力量     dp[i][j] 表示前i个装备 花费j元 所得的最大力量        此处的装备应该只高级装备 低级装备会算进高级装备里面    我们有 dp[num][j]=max{dp[num-1][k]+f[i][l][j-k]}         一共是 i，j，k，l 四重循环         i是第几个高级装备 j是前i装备一共花费         k是前i-1类装备的花费 c是这个装备里有多少用于合成其他装备    每个高级装备是树根 儿子们是合成它所要的低级装备     处理每一个高级装备 有        g[i][j] 表示此装备的钱i个儿子 花费j的钱 所获得的最大力量        那么g[i][j]=max{g[i-1][j-k]+f[v][l*need][k]}        有 i，j，k，l四层循环        i表示前i个儿子 j表示总共花费 l表示合成多少个该装备         k表示合成该装备的花费 v表示儿子节点         need表示合成一个该装备需要多少这个儿子                  之后枚举合成的l个物品中有j个是直接用于增加力量的 剩余的参加合成        f[i][j][k] =max{g[num][k]+P[i]*(l-j)}         其中num是指所有儿子      处理每一个低级装备 枚举用来合成的 和剩下直接加力量的 dp一遍就return */#include<cstdio> #include<cstring>#define inf (0x3fffffff)#define max(a,b) ((a>b)?(a):(b)) #define min(a,b) ((a>b)?(b):(a)) using namespace std;const int N=60,NN=2050;struct pp {int v,need,nxt;} e[NN*10];int n,m,tot,P[N],L[N],M[N],head[N],du[N];int f[N][2*N][NN],g[N][NN],dp[N][NN];char str[6];void add(int u,int v,int need){    e[++tot].nxt=head[u];head[u]=tot;    e[tot].v=v;e[tot].need=need;du[v]++;}void init(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%d",&P[i]); scanf("%s",str);        if(str[0]==‘A‘)        {            int num;scanf("%d",&num);            for(int j=1,v,need;j<=num;j++)                scanf("%d%d",&v,&need),add(i,v,need);        }        else scanf("%d%d",&M[i],&L[i]);    }}void DP(int x){    if(!head[x])  // 此为基础装备     {        L[x]=min(L[x],m/M[x]);        for(int i=0;i<=L[x];i++) //用于合成         for(int j=i;j<=L[x];j++) // （j-i）用于直接加力量            f[x][i][j*M[x]]=(j-i)*P[x];  return ;        // 这里更新 f  错写成了M[i] ...    }    L[x]=inf; // 高级装备无限制！    for(int j=head[x];j;j=e[j].nxt)    {        int v=e[j].v,need=e[j].need;DP(v);        L[x]=min(L[x],L[v]/need); // 更新L[x] 要合成当然取最小啦        M[x]+=need*M[v];    } // 这里更新高级装备的 L 和 M      L[x]=min(L[x],m/M[x]);    memset(g,~0x3f,sizeof(g)); g[0][0]=0;    for(int l=L[x];l>=0;l--)    {        int num=0;        for(int i=head[x];i;i=e[i].nxt)        {            int v=e[i].v,need=e[i].need; num++;            //  g[i][j]=max{g[i-1][j-k]+f[v][l*need][k]}            for(int j=0;j<=m;j++)            for(int k=0;k<=j;k++)                g[num][j]=max(g[num][j],g[num-1][j-k]+f[v][l*need][k]);            // 这里计算该装备的g         }        // f[i][j][k] =max{g[num][k]+P[i]*(l-j)}         for(int j=0;j<=l;j++)        for(int k=0;k<=m;k++)            f[x][j][k]=max(f[x][j][k],g[num][k]+P[x]*(l-j));        // 这里更新 f   剩下l-j就是用来直接加力量的了     }}void solve(){    memset(f,~0x3f,sizeof(f));    int num=0,ans=0;    for(int i=1;i<=n;i++) if(!du[i]) // 只对高级装备 dp     {        DP(i); num++;// dp[num][j]=max{dp[num-1][k]+f[i][l][j-k]}         for(int j=0;j<=m;j++)        for(int k=0;k<=j;k++)        for(int l=0;l<=L[i];l++)            dp[num][j]=max(dp[num][j],dp[num-1][k]+f[i][l][j-k]);    }    for(int i=0;i<=m;i++) ans=max(ans,dp[num][i]);    printf("%d\n",ans);}int main(){    init();    solve();    return 0;}