【BZOJ1017】【JSOI2008】魔兽地图

~~力丸的散夜对剑！~~

好迷的DP，不会写。。学习了一番hzwer的做法，好像复杂度也挺诡异。。

花式背包。。跑若干次背包。。

// <1017.cpp> - Fri Mar 10 16:45:31 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
#define next NEXT
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int N=55;
const int M=2010;
const int INF=1e9;
int bt,b[N],next[N],to[N],val[N],rd[N];
inline void add(int x,int y,int z){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;
    rd[y]++;
}
int n,m,a[N],p[N],t[N],f[N][110][M],g[N][M],v[N][M];
void work(int x){
    if(!b[x]){
        for(int i=0;i<=t[x];i++)
            for(int j=i;j<=t[x];j++)f[x][i][j*p[x]]=(j-i)*a[x];
        return;
    }
    t[x]=INF;
    for(int i=b[x];i;i=next[i]){
        work(to[i]);
        t[x]=min(t[x],t[to[i]]/val[i]);
        p[x]+=val[i]*p[to[i]];
    }
    t[x]=min(t[x],m/p[x]);
    memset(g,192,sizeof(g));
    g[0][0]=0;
    for(int i=t[x];i>=0;i--){
        int cnt=0;
        for(int j=b[x];j;j=next[j]){
            cnt++;
            for(int k=0;k<=m;k++)
                for(int c=0;c<=k;c++)
                    g[cnt][k]=max(g[cnt][k],g[cnt-1][k-c]+f[to[j]][i*val[j]][c]);
        }
        for(int j=0;j<=i;j++)
            for(int k=0;k<=m;k++)f[x][j][k]=max(f[x][j][k],g[cnt][k]+(i-j)*a[x]);
    }
}
int main(){
    n=gi(),m=gi();
    for(int i=1;i<=n;i++){
        a[i]=gi();
        if(getchar()=='A'){
            int c=gi();
            while(c--){int y=gi(),z=gi();add(i,y,z);}
        }else p[i]=gi(),t[i]=min(gi(),m/p[i]);
    }
    memset(f,192,sizeof(f));
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(rd[i])continue;
        work(i);
        cnt++;
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j;k++)
                v[cnt][j]=max(v[cnt][j],v[cnt-1][k]+f[i][0][j-k]);
    }
    int ans=0;
    for(int i=0;i<=m;i++)ans=max(ans,v[cnt][i]);
    printf("%d",ans);
    return 0;
}

// <1017.cpp> - Fri Mar 10 16:45:31 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

#define next NEXT

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int N=55;

const int M=2010;

const int INF=1e9;

int bt,b[N],next[N],to[N],val[N],rd[N];

inline void add(int x,int y,int z){

next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;

rd[y]++;

}

int n,m,a[N],p[N],t[N],f[N][110][M],g[N][M],v[N][M];

void work(int x){

if(!b[x]){

for(int i=0;i<=t[x];i++)

for(int j=i;j<=t[x];j++)f[x][i][j*p[x]]=(j-i)*a[x];

return;

}

t[x]=INF;

for(int i=b[x];i;i=next[i]){

work(to[i]);

t[x]=min(t[x],t[to[i]]/val[i]);

p[x]+=val[i]*p[to[i]];

}

t[x]=min(t[x],m/p[x]);

memset(g,192,sizeof(g));

g[0][0]=0;

for(int i=t[x];i>=0;i--){

int cnt=0;

for(int j=b[x];j;j=next[j]){

cnt++;

for(int k=0;k<=m;k++)

for(int c=0;c<=k;c++)

g[cnt][k]=max(g[cnt][k],g[cnt-1][k-c]+f[to[j]][i*val[j]][c]);

}

for(int j=0;j<=i;j++)

for(int k=0;k<=m;k++)f[x][j][k]=max(f[x][j][k],g[cnt][k]+(i-j)*a[x]);

}

int main(){

n=gi(),m=gi();

for(int i=1;i<=n;i++){

a[i]=gi();

if(getchar()=='A'){

int c=gi();

while(c--){int y=gi(),z=gi();add(i,y,z);}

}else p[i]=gi(),t[i]=min(gi(),m/p[i]);

}

memset(f,192,sizeof(f));

int cnt=0;

for(int i=1;i<=n;i++){

if(rd[i])continue;

work(i);

cnt++;

for(int j=0;j<=m;j++)

for(int k=0;k<=j;k++)

v[cnt][j]=max(v[cnt][j],v[cnt-1][k]+f[i][0][j-k]);

}

int ans=0;

for(int i=0;i<=m;i++)ans=max(ans,v[cnt][i]);

printf("%d",ans);

return 0;

}