力丸的散夜对剑!
好迷的DP,不会写。。学习了一番hzwer的做法,好像复杂度也挺诡异。。
花式背包。。跑若干次背包。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
// <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; } |