[JSOI2008]魔兽地图DOTR

第一行包含两个整数，N (1 ≤ n ≤ 51) 和 m (0 ≤ m ≤ 2,000)。分别表示装备的种类数和金币数。装备用1到N的整数编号。
接下来的N行，按照装备1到装备n的顺序，每行描述一种装备。每一行的第一个非负整数表示这个装备贡献的力量值。接下来的非空字符表示这种装备是基本装备还是高级装备，A表示高级装备，B表示基本装备。
如果是基本装备，紧接着的两个正整数分别表示它的单价（单位为金币）和数量限制（不超过100）。
如果是高级装备，后面紧跟着一个正整数C，表示这个高级装备需要C种低级装备。后面的2C个数，依次描述某个低级装备的种类和需要的个数。

C++11(clang++ 3.9) 解法, 执行用时: 808ms, 内存消耗: 45756K, 提交时间: 2019-10-23 20:15:43

#include <cstdio>
#include <cstring>

inline bool isdig(char c)
{
	return c>='0'&&c<='9';
}

inline bool isupp(char c)
{
	return c>='A'&&c<='Z';
}

inline char getch(void)
{
	static char buf[100000],*p1=buf,*p2=buf;

	if(p1!=p2) return *p1++;

	p1=buf;
	p2=p1+fread(buf,1,100000,stdin);

	return p1==p2?EOF:*p1++;
}

template<class T> inline void read(T &num)
{
	bool neg=false;
	char c=getch();

	num=(T)0;
	while(!isdig(c))
	{
		neg|=(c=='-');
		c=getch();
	}
	while(isdig(c))
	{
		num=num*10+c-'0';
		c=getch();
	}
	num=neg?-num:num;

	return;
}

template<typename T> inline T max(T a,T b)
{
	return a>b?a:b;
}

template<typename T> inline T min(T a,T b)
{
	return a<b?a:b;
}

const int N=55,M=2005,L=105,inf=0x3f3f3f3f;
struct EDGE
{
	int nxt,to,val;
	
	EDGE(int n=0,int t=0,int v=0):nxt(n),to(t),val(v){}
}edge[N*N];
int n,m,cnt,wor[N],pri[N],lim[N],head[N],dp[N][L][M],tmp[M],ans[M];
bool vis[N],used[N];

inline void add_edge(int u,int v,int w)
{
	edge[++cnt]=EDGE(head[u],v,w);
	head[u]=cnt;
	
	return;
}

void dfs(int u)
{
	if(vis[u]) return;
	vis[u]=true;
	if(!head[u])
	{
		for(int i=lim[u];i>=0;--i)
			for(register int j=i;j<=lim[u];++j) dp[u][i][j*pri[u]]=wor[u]*(j-i);
		
		return;
    }
	lim[u]=inf;
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int v=edge[i].to,w=edge[i].val;
		
		dfs(v);
		lim[u]=min(lim[u],lim[v]/w);
		pri[u]+=pri[v]*w;
	}
	lim[u]=min(lim[u],m/pri[u]);
	for(int i=lim[u];i>=0;--i)
	{
		memset(tmp,-0x3f,sizeof(tmp));
		tmp[0]=0;
		for(int j=head[u];j;j=edge[j].nxt)
		{
			int v=edge[j].to,w=edge[j].val;
			
			for(int k=m;k>=0;--k)
			{
				int t=-inf;
				
				for(register int l=0;l<=k;++l) t=max(t,tmp[k-l]+dp[v][i*w][l]);
				tmp[k]=t;
			}
		}
		for(int j=0;j<=i;++j)
			for(register int k=0;k<=m;++k) dp[u][j][k]=max(dp[u][j][k],tmp[k]+wor[u]*(i-j));
	}
	
	return;
}
int main()
{
	int c,ki,nd;
	char kd;
	
	read(n);
	read(m);
	for(int i=1;i<=n;++i)
	{
		read(wor[i]);
		kd=getch();
		while(!isupp(kd)) kd=getch();
		if(kd=='A')
		{
			read(c);
			while(c--)
			{
				read(ki);
				read(nd);
				
				add_edge(i,ki,nd);
				used[ki]=true;
			}
		}
		else
		{
			read(pri[i]);
			read(lim[i]);
			
			lim[i]=min(lim[i],m/pri[i]);
		}
	}
	
	memset(dp,-0x3f,sizeof(dp));
	for(int i=1;i<=n;++i)
		if(!used[i])
		{
			dfs(i);
			for(int j=m;j>=0;--j)
				for(register int k=0;k<=j;++k) ans[j]=max(ans[j],ans[j-k]+dp[i][0][k]);
		}
	
	printf("%d",ans[m]);
	return 0;
}

详情