1 #include <stdio.h>
2 #define MAXR 201
3 int maxt,tn,tl[MAXR],tr[MAXR],tc[MAXR],tv[MAXR],opt[MAXR][601];
4 bool vis[MAXR][601]={false};
5 int inline max(int a,int b)
6 {
7 return a>b?a:b;
8 }
9 int inline min(int a,int b)
10 {
11 return a<b?a:b;
12 }
13 int tdp(int vex,int t)
14 {
15 if(t<tc[vex])return 0;
16 t-=tc[vex];
17 if(vis[vex][t])return opt[vex][t];
18 if(tv[vex])
19 return vis[vex][t]=true,opt[vex][t]=min(t/5,tv[vex]);
20 int curmax=0,tt=t-tc[tr[vex]];
21 for(int ltime=tc[tl[vex]];ltime<=tt;++ltime)
22 curmax=max(curmax,tdp(tl[vex],ltime)+tdp(tr[vex],t-ltime));
23 curmax=max(curmax,max(tdp(tl[vex],t),tdp(tr[vex],t)));
24 return vis[vex][t]=true,opt[vex][t]=curmax;
25 }
26 void input(int cur)
27 {
28 int t1,t2;
29 scanf("%d%d",&t1,&t2);
30 tc[cur]=t1<<1;
31 if(t2)
32 {tv[cur]=t2;return ;}
33 tl[cur]=++tn;input(tn);
34 tr[cur]=++tn;input(tn);
35 }
36 int main()
37 {
38 freopen("gallery.in","r",stdin);
39 freopen("gallery.out","w",stdout);
40 scanf("%d",&maxt);
41 input(0);
42 printf("%d\n",tdp(0,maxt-1));
43 return 0;
44 }
45
上面的是Gallery.cpp
1 #include <stdio.h>
2 #define F(a,b,c) for(int a=b;a<=c;++a)
3 #define MAXN 1501
4 //#define DEBUG //switch to DEBUG
5 const int inf = MAXN;
6 int vn,gt[MAXN][MAXN],f[MAXN][2],ind[MAXN],root;
7 int inline min(int a,int b)
8 {
9 return a<b?a:b;
10 }
11 int inline abs(int x)
12 {
13 return x>0?x:-x;
14 }
15 void tdp(int v)
16 {
17 int *tmp=gt[v];//sum=0,add=inf;
18 F(i,1,tmp[0])
19 tdp(gt[v][i]);
20 f[v][0]=1;
21 F(i,1,tmp[0])
22 {
23 //int cache=min(f[tmp[i]][0],f[tmp[i]][1]);
24 f[v][0]+=min(f[tmp[i]][0],f[tmp[i]][1]); //!!??
25 f[v][1]+=f[tmp[i]][0];
26 //add=min(add,abs(cache-f[tmp[i]][0]));
27 //sum+=cache;
28 }
29 //if(!tmp[0])f[v][1]=inf;
30 ////////// debug {{{
31 #ifdef DEBUG
32 printf("f[%d][0]=%d\nf[%d][1]=%d\n",v,f[v][0],v,f[v][1]);
33 #endif
34 ////////////// }}}
35 }
36 int main()
37 {
38 freopen("soldier.in","r",stdin);
39 freopen("soldier.out","w",stdout);
40 scanf("%d",&vn);
41 F(i,1,vn)
42 {
43 int curv,*tmp;
44 scanf("%d",&curv);
45 tmp=gt[curv];
46 scanf("%d",tmp);
47 F(j,1,gt[curv][0])
48 {
49 scanf("%d",tmp+j);
50 ++ind[tmp[j]];
51 }
52 }
53 F(i,0,vn-1)
54 if(!ind[i])root=i;
55 tdp(root);
56 printf("%d\n",min(f[root][0],f[root][1]));
57 return 0;
58 }
上面的是Soldier.cpp
posted on 2010-04-11 13:17
夏雨 阅读(364)
评论(3) 编辑 收藏 引用