C++博客-Aluex's Blog

[第三次函授作业]

夏雨 — Sun, 16 May 2010 07:25:00 GMT

[第三次函授作业]

点此查看

夏雨 2010-05-16 15:25 发表评论

[第二次函授作业]

夏雨 — Sun, 11 Apr 2010 07:43:00 GMT

第二次函授作业

点此查看

夏雨 2010-04-11 15:43 发表评论

春季函授第一次作业的代码

夏雨 — Sun, 11 Apr 2010 05:17:00 GMT

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

夏雨 2010-04-11 13:17 发表评论