随笔 - 7  文章 - 4  trackbacks - 0
<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

[第三次函授作业]

点此查看

posted @ 2010-05-16 15:25 夏雨 阅读(89) | 评论 (0)编辑 收藏
第二次函授作业

点此查看


posted @ 2010-04-11 15:43 夏雨 阅读(70) | 评论 (0)编辑 收藏
 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 @ 2010-04-11 13:17 夏雨 阅读(145) | 评论 (3)编辑 收藏
第一题
该题主要考察了树形动归。根本原型是个背包。
定义状态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日以后贴上来。
posted @ 2010-03-20 12:10 夏雨 阅读(67) | 评论 (0)编辑 收藏
函授第一次作业已经发布,点击这里可以查看题目(丢了个图)
已经完成。具体解题报告将会在下周日之前贴上来。
不早了,睡觉去~

posted @ 2010-03-14 23:14 夏雨 阅读(161) | 评论 (0)编辑 收藏
江苏省信息学奥林匹克春季函授于3月10日开始。
我也报了名。。(还有些小插曲)
之后,我会把题目及解题思路贴上来。
第一次作业将于3月10日布置。
posted @ 2010-03-07 12:49 夏雨 阅读(77) | 评论 (0)编辑 收藏
注册了新的博客。
目前打算:
1.将在这里贴上OI相关的代码,和生活琐事
2.由于学校学习忙碌,暂且打算每周更新一次。
This will be a NEW FRESH start.
posted @ 2010-02-27 17:55 夏雨 阅读(77) | 评论 (1)编辑 收藏
仅列出标题