注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

2014年09月02日  

2014-09-02 10:27:37|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

信息学夏令营的后几天...(10)2008-07-24 07:01 P.M.

 (2009-03-15 21:04:49)
标签: 

杂谈


信息学夏令营的后几天...(9)2008-07-24 07:01

 (2009-03-15 21:06:25)
标签: 

杂谈

2

a[i]保存第i首歌曲的长度。

data[i,j]=用1张盘可以保存ij首歌曲之间最多的歌曲数目。

Ans[i,j]=i首歌用j张盘可以录制的最多数量。

状态转移方程:

   ans[i,j]=max{ans[k-1,j-1]+data[k,i]}

        (1<=k<=i)

一部分是用j-1张盘把前k-1首歌能录制的最大数量,另一部分是用一张盘在第k到第i首歌之间能录制的数量。

目标:ans[n,m]

b:array[0..maxn] of integer;    //b[1]开始临时记录ij的歌曲

sum:array[0..maxn] of integer; //记录和sum[i]=b[1]+...+b[i]

readln(n,v,m);

for i:=1 to n do read(a[i]);

for i:=1 to n do     //起点i

     begin

       num:=0; //ij能用一张盘刻的最多歌曲数量

     b[0]:=0; sum[0]:=0;

       for j:=i to n do //终点j

         begin

           k:=num;

           while a[j]<b[k] do //插入排序ij的歌曲

             begin b[k+1]:=b[k]; sum[k+1]:=sum[k]+a[j]; dec(k);end;

           b[k+1]:=a[j]; sum[k+1]:=sum[k]+a[j];

           if sum[num+1]<=v then inc(num);

                 //如果最后一项的sum值小于一张唱片的长度,则num1

           data[i,j]:=num;    

         end;

     end;

fillchar(ans,sizeof(ans),0);

for i:=1 to n do

   for j:=1 to m do

      for k:=1 to i do

         ans[i,j]:=max(ans[i,j],ans[k-1,j-1]+data[k,i]);

8、集装箱问题

9、最大m子段和问题

   f[i,j]:1到第i数中,取j段的最大和。

f[i,j]=max{f[k,j-1]+d[k+1,i]}

    (j-1<=k<=i-1)

d[k+1,i]:k+1到第i个中取一个最大子段的和,动规

目标:f[n,m]

721 13:00-15:50 BFS

主讲:咱们的兄弟wjd!!!

 

一、            广度优先搜索

1、图的遍历

2、求连通子图的个数

1:赛跑

2:子图划分

3、求无权图的单源最短路

 

 

二、            

1、无向图的传递闭包(用于计算图的连通性和图中满足条件的连通分支--辨别任两点之间是否有路径

   for k1 to n do {枚举中间顶点}

for i1 to n do{枚举所有顶点对}

   for j1 to n do {计算顶点i和顶点j的连通情况}

longlink[ij]longlink[ij]or(longlink[ik]andlonglink[kj])

应用:

1、传递闭包每一行(列)中值为ture的元素代表对应顶点所在的连通分量

2、将布尔变量改为路径长度、将内循环的布尔表达式改为比较路径长短的数值表达式,即可求任一对顶点间的最长路和最短路。

弊病:

1、有约束条件:求任一对顶点间的最长路时不能出现正权回路;求最短路时不能出现负权回路。

2、虽然编程简单,但时间效率低下

例子:染色

2、如何计算图的最小点基,至少添多少边才可使有向图变成强连通图

思路:计算所有强连通子图,并化为点,在进行处理。

例子:网络

    最高/低强连通分支:只有入边/出边的强连通分支

    最高强连通分支每个都必须包含点基内的点

3、最小生成树

(1)   kruskal 依次选择边权最小的不形成回路的边,加入集合

   Const

maxn=200; maxe=maxn*maxn;{顶点数和边数的上限}

Type

edgetype=Record{边的类型}

            x,y,c:longint;{边权为c的边(xy}

           End;

Var

e:Array [1..maxe] of edgetype;{边集,其中第i条边为(e[i].x,e[i].y),该边的权为e[i].c}

n,m,ans:longint;{顶点数为n,边数为m}

f:Array [1..maxn] of longint;{并查集。其中f[i]为顶点i所在并查集的代表顶点,即子树根}

Function top(i:longint):longint;{计算和返回顶点i所在并查集的代表顶点}

Begin

if i<>f[i] Then f[i]top(f[i]);{i非所在并查集的代表顶点,则沿f[i]递归}

topf[i];{返回顶点i所在并查集的代表顶点}

End;{top}

现有边权为c的边(ij)。若该边的两个端点分属于两棵树,顶点i和顶点j所在子树的根分别为xv,则(i,j) 加入最小生成树,合并两棵树(即顶点i和顶点j所在的并查集)。

Procedure Union(i,j,c:longint);{合并ij所在集合}

Var

x,y:longint;

Begin

xtop(i); ytop(j);{分别取出顶点i和顶点j所在子树的根}

if x<>y Then Begin inc(ans,c);f[y]x;End;{ij分属于两棵子树,则该边权计入最小生成树的权和,两棵子树合并}

End;{ Union }

 

(2)   prim

fillchar(basizeof(ba)0) {所有顶点未在生成树}

for i=2 to n do d[i]=∞; {所有顶点的距离值初始化}

d[1]=0 ans=0{顶点1的距离值和生成树的权和初始化}

for i=1 to n do begin {依次范围每个顶点}

min=oo{在所有未在生成树、且距离值最小(min)的顶点k}

for j=1 to n do

    if not ba[j]and(d[j]<min)

      then begin k=jmin=d[j]end{then}

if min=then begin ans=-1breakend{若这样的顶点不存在,则无解退出}

ans=ans+minba[k]=true{最小距离值min计入生成树的权和,顶点k进入生成树}

for j=1 to n do{调整与k相连的各顶点的距离值}

   begin

     min=w[kj]if min<d[j] then d[j]=min

   end{for}

end{for}

writeln(ans03) {输出最小生成树的权和}

 

722 1430~1730 dfs

主讲:wjd

 

一、            

1、计算最大边权最小的生成树(求最小生成树)

2、例题:

(1)    机器蛇

1)判断线段相交:坐标计算向量叉乘x1*y2-x2*y1

2)使用最小生成树

3)程序

信息学夏令营的后几天...(11)2008-07-24 07:02 P

 (2009-03-15 21:03:46)
标签: 

杂谈

begin

v=(p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x)

if v=0 then cp=0 else if v>0 then cp=1 else cp=-1

end{cp}

function dist(abinteger)longint{ 计算第a条机器蛇和第b条机器蛇间的距离,若ab之间有屏蔽,则距离设为无穷大 }

var

iinteger

begin

dist=oo

for i=1 to m do { 如果ab穿过第i个屏蔽,则返回无穷大 }

    if (cp(w1[i]w2[i]s[a])*cp(w1[i]w2[i]s[b])=-1) and

       (cp(s[a]s[b]w1[i])*cp(s[a]s[b]w2[i])=-1) then exit

dist=sqr(s[a].x-s[b].x)+sqr(s[a].y-s[b].y)

end{ dist }

begin

read(n){ 读入数据 }

for i=1 to n do with s[i] do read(xy)

read(m)

for i=1 to m do read(w1[i].xw1[i].yw2[i].xw2[i].y)

{Prim算法求最小生成树 }

fillchar(basizeof(ba)0) {所有机器蛇未访问}

for i=2 to n do d[i]=oo {最短边长序列初始化}

d[1]=0 ans=0 {从机器蛇1出发,通信网的最短长度初始化}

   for i=1 to n do begin {访问n条机器蛇}

   min=oo{在所有未访问的机器蛇中寻找与已访问的机器蛇相连且具有最短边长的机器蛇k}

    for j=1 to n do

     if not ba[j] and (d[j]<min) then begin k=j min=d[j]end{then}

if min=oo then begin ans=-1 break end{then}{若这样的机器蛇不存在,则无解退出}

ans=ans+sqrt(min) ba[k]=true {最短边长计入通信网,机器蛇k已访问}

for j=1 to n do {机器蛇k出发的所有不受屏蔽的边中,寻找边长最短的(kj}

    begin min=dist(kj) if min<d[j] then d[j]=min end{for}

end{for}

writeln(ans03) {输出通信网的最短长度}

end.{main}

(1)    北极通讯网络

       构图:任两个村庄连边,边长为欧式距离;

求最小生成树

计算和输出最小生成树的第k长的边

(2)    机器人

       依次处理每段墙:

         将当前强转换为图;

         计算最小生成树的最长边max;

          if max<ans then ans=max;

输出最长边长ans


 

  评论这张
 
阅读(25)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017