随笔档案

 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 

 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 }

第一题

该题主要考察了树形动归。根本原型是个背包。
定义状态f[i][j]为第i个节点给实际j时间（减去路上的消耗）所能偷得的画数。
方程可以轻易得出：f[i][j]=max(f[k][l],f[k][j-l])(k为i的儿子节点）

第二题

该题同样是树形动态规划。
定义状态f[i][0]为第i点不放士兵的最优解
f[i][1]为第i点放士兵的最优解
则
f[i][0]=sum(f[k][1])
f[i][1]=sum(min(f[k][0],f[k][1]))
这题就Over了。

本次作业的完整代码会在4月10日以后贴上来。

之后，我会把题目及解题思路贴上来。

第一次作业将于3月10日布置。

目前打算：
1.将在这里贴上OI相关的代码，和生活琐事
2.由于学校学习忙碌，暂且打算每周更新一次。