1 条题解
-
-1
#include<bits/stdc++.h> using namespace std; const int N=55,M=2e3+5,K=1e2+5; const int inf=0x3f3f3f3f; struct edge{ int x,y,c,pre; }a[M]; int last[N],alen; void ins(int x,int y,int c){ a[++alen]=edge{x,y,c,last[x]}; last[x]=alen; } int n,m,vis[N],cost[N],lim[N],v[N]; int f[N][K][M],g[M]; void dfs(int x){ if(!x){ for(int k=last[x];k;k=a[k].pre){ int y=a[k].y; dfs(y); for(int u=m;u>=0;u--) for(int v=0;v<=u;v++) f[x][0][u]=max(f[x][0][u],f[x][0][u-v]+f[y][0][v]); } return; } if(!last[x]){ lim[x]=min(lim[x],m/cost[x]); for(int i=lim[x];i>=0;i--) for(int j=i;j<=lim[x];j++) f[x][i][j*cost[x]]=(j-i)*v[x]; return; } lim[x]=inf; for(int k=last[x];k;k=a[k].pre){ int y=a[k].y; dfs(y); lim[x]=min(lim[x],lim[y]/a[k].c); cost[x]+=cost[y]*a[k].c; } lim[x]=min(lim[x],m/cost[x]); for(int j=0;j<=lim[x];j++){ for(int i=0;i<=m;i++){ g[i]=-inf; } g[0]=0; for(int k=last[x];k;k=a[k].pre){ int y=a[k].y; for(int u=m;u>=0;u--){ int mx=-inf; for(int v=0;v<=u;v++){ mx=max(mx,g[u-v]+f[y][j*a[k].c][v]); } g[u]=mx; } } for(int i=0;i<=j;i++) for(int l=0;l<=m;l++) f[x][i][l]=max(f[x][i][l],g[l]+(j-i)*v[x]); } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=0;j<K;j++) for(int k=0;k<=m;k++) f[i][j][k]=-inf; for(int x=1;x<=n;x++){ scanf("%d",&v[x]); char op[10];scanf("%s",op+1); if(op[1]=='A'){ int cnt;scanf("%d",&cnt); for(int j=1;j<=cnt;j++){ int y,c;scanf("%d%d",&y,&c); ins(x,y,c); vis[y]=1; } } if(op[1]=='B'){ scanf("%d%d",&cost[x],&lim[x]); } } for(int i=1;i<=n;i++){ if(!vis[i]){ ins(0,i,0); } } dfs(0); int ans=0; for(int i=1;i<=m;i++){ ans=max(ans,f[0][0][i]); } printf("%d",ans); return 0; }
- 1
信息
- ID
- 1017
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 47
- 已通过
- 15
- 上传者