[bzoj1017][JSOI2008]魔兽地图 DotR (Tree DP)【有待优化】

  1 /*====================Asm.Def========================*/
  2 #include <iostream>
  3 #include <cctype>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <ctime>
  8 #include <queue>
  9 using namespace std;
 10 inline void getd(int &x){
 11     char c = getchar();
 12     bool minus = 0;
 13     while(!isdigit(c) && c != ‘-‘)c = getchar();
 14     if(c == ‘-‘)minus = 1, c = getchar();
 15     x = c - ‘0‘;
 16     while(isdigit(c = getchar()))x = x * 10 + c - ‘0‘;
 17     if(minus)x = -x;
 18 }
 19 /*======================================================*/
 20 const int maxn = 53, maxm = 2003, maxc = 102, INF = 0x7fffffff;
 21 typedef long long LL;
 22 struct Node{
 23     Node *son, *bro;
 24     int maxcost, maxcnt, cnt, pri, val;
 25     int f[maxc][maxm], S[maxc][maxm];
 26     void dfs();
 27     void dp();
 28 }node[maxn], *Root;
 29 int N, M, tmp[maxm];
 30 
 31 void Node::dfs(){
 32     if(son == NULL){
 33         maxcnt = min(M / pri, maxcnt);
 34         if((LL)maxcnt * pri > M)maxcnt = 0, maxcost = 0;
 35         else maxcost = maxcnt * pri;
 36         return;
 37     }
 38     Node *it = son;
 39     maxcnt = INF;
 40     while(it != NULL){
 41         it->dfs();
 42         maxcost = min(M, maxcost + it->maxcost);
 43         if((LL)it->pri * it->cnt > M)
 44             pri = 0, maxcnt = 0;
 45         else{
 46             pri += it->pri * it->cnt;
 47             maxcnt = min(maxcnt, it->maxcnt / it->cnt);
 48         }
 49         it = it->bro;
 50     }
 51     if(pri)maxcnt = min(M / pri, maxcnt);
 52     else maxcnt = 0;
 53 }
 54 
 55 inline void init(){
 56     getd(N), getd(M);
 57     unsigned long long NotRoot = 1;
 58     int i, j, k, ch;
 59     for(i = 1;i <= N;++i){
 60         getd(node[i].val);
 61         while(!isalpha(ch = getchar()));
 62         if(ch == ‘A‘){
 63             getd(j);getd(k);
 64             getd(node[k].cnt);
 65             node[i].son = node + k;
 66             NotRoot |= (1ll << k);
 67             while(--j){
 68                 getd(k);getd(node[k].cnt);
 69                 node[k].bro = node[i].son;
 70                 node[i].son = node + k;
 71                 NotRoot |= (1ll << k);
 72             }
 73         }
 74         else
 75             getd(node[i].pri), getd(node[i].maxcnt);
 76     }
 77     NotRoot = (~NotRoot) & (NotRoot + 1);
 78     i = 0;
 79     while(NotRoot > 1)++i, NotRoot >>= 1;
 80     Root = node + i;
 81     Root->dfs();
 82 }
 83 
 84 inline void AddTo(int *S, int *f, int limS, int limf){
 85     int i, j;
 86     for(i = 1;i <= limS;++i){
 87         tmp[i] = 0;
 88         for(j = 0;j <= min(limf, i);++j)if(f[j] + S[i-j] > tmp[i])
 89             tmp[i] = f[j] + S[i-j];
 90     }
 91     for(i = 1;i <= limS;++i)S[i] = tmp[i];
 92 }
 93 
 94 void Node::dp(){
 95     int i, j;
 96     Node *it;
 97     if(son != NULL)for(it = son;it != NULL;it = it->bro){
 98         it->dp();
 99         for(i = 0;i <= maxcnt;++i)
100             AddTo(S[i], it->f[i*it->cnt], maxcost, it->maxcost);
101         for(j = 1;j <= maxcost;++j)
102             f[maxcnt][j] = max(S[maxcnt][j], f[maxcnt][j-1]);
103     }
104     for(i = maxcnt-1;i >= 0;--i)for(j = 1;j <= maxcost;++j){
105         f[i][j] = max(f[i][j-1], S[i][j]);
106         if(j >= pri && f[i+1][j-pri] + val > f[i][j])
107             f[i][j] = f[i+1][j-pri] + val;
108     }
109 }
110 
111 int main(){
112     #if defined DEBUG
113     freopen("test", "r", stdin);
114     #else
115     freopen("bzoj_1017.in", "r", stdin);
116     freopen("bzoj_1017.out", "w", stdout);
117     #endif
118     init();
119     
120     Root->dp();
121     printf("%d\n", Root->f[0][Root->maxcost]);
122     
123     #if defined DEBUG
124     cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
125     #endif
126     return 0;
127 }