ITeye博客

玉箫客

玉箫客 · 共 11 篇文章

[置顶] 动态规划

动态规划算法 一、基本概念 动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划。 二、基本思想与策略 基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。 由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段…

2012-07-07 10:21 · 程序设计 · 评论(0)

杭电1162 最小生成树问题

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162 Problem Description: Eddy begins to like painting pictures recently ,he is sure of himself to become a painter.Every day Eddy draws pictures in his small room, and he usually puts out his newest pictures to let his friends appreciate. but the resu…

2012-07-27 15:15 · 程序设计 · 评论(0)

杭电1596 迪杰特斯拉算法的应用

题目 Problem Description XX星球有很多城市,每个城市之间有一条或多条飞行通道,但是并不是所有的路都是很安全的,每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0,1),一条从u 到 v 的通道P 的安全度为Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的边 ,现在8600 想出去旅游,面对这这么多的路,他想找一条最安全的路。但是8600 的数学不好,想请你帮忙 ^_^ Input 输入包括多个测试实例,每个实例包括: 第一行:n。n表示城市的个数n<=1000; 接着是一个n*n的矩阵表示两个城市之间的安全系数,(0可以理…

2012-07-25 20:47 · 程序设计 · 评论(0)

杭电2680 迪杰特斯拉算法的应用

题目描述: Problem Description: One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may sup…

2012-07-25 20:43 · 程序设计 · 评论(0)

杭电1272

这道题主要就是判断一下有没有环,还有就是节点数减去边数等于1,还有就是一个集合,,空集合时也符合题意,这样就可以了······· 题目: 小希的迷宫 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9415 Accepted Submission(s): 2757 Problem Description 上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首…

2012-07-18 15:13 · 程序设计 · 评论(0)

杭电2544 最短路径

Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗? Input 输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,…

2012-07-17 17:31 · 程序设计 · 评论(0)

迪杰斯特拉(Dijkstra)算法

迪杰斯特拉算法 迪杰斯特拉(Dijkstra)算法思想 按路径长度递增次序产生最短路径算法: 把V分成两组: (1)S:已求出最短路径的顶点的集合 (2)V-S=T:尚未确定最短路径的顶点集合,将T中顶点按最短路径递增的次序加入到S中,保证:(1)从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度 (2)每个顶点对应一个距离值S中顶点:从V0到此顶点的最短路径长度T中顶点:从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和(反证法可证) 求最短…

2012-07-17 16:07 · 程序设计 · 评论(0)

笔记本作无线路由

开启windows 7的隐藏功能:虚拟WiFi和SoftAP(即虚拟无线AP),就可以让电脑变成无线路由器,实现共享上网。 点开始 所有程序 命令提示符右键管理员身份运行命令提示符 运行命令:netsh wlan set hostednetwork mode=allow ssid=wuminPC key=wuminWiFi 此命令有三个参数,mode:是否启用虚拟WiFi网卡,改为disallow则为禁用 。 ssid:无线网名称,最好用英文(以wuminPC为例)。 key:无线网密码,八个以上字符(以wuminWiFi为例)。 以上三个参数可以自己设置,例如只使用mode=disallo…

2012-07-08 17:16 · 笔记本 · 评论(0)

杭电acm部分题目分类

注:DP代表动态规划 1001 这个就不用说了吧 1002 简单的大数 1003 DP经典问题,最大连续子段和 1004 简单题 1005 找规律(循环点) 1006 感觉有点BT的题,我到现在还没过 1007 经典问题,最近点对问题,用分治 1008 简单题 1009 贪心 1010 搜索题,剪枝很关键 1011 1012 简单题 1013 简单题(有个小陷阱) 1014 简单题 1015 可以看作搜索题吧 1016 经典的搜索 1017 简单数学题 1018 简单数学题 1019 简单数学题 1020 简单的字符串处理 1021 找规律的数学题 1022 数据结构的题(栈的应用) 102…

2012-07-07 16:38 · 程序设计 · 评论(0)

动态规划之背包问题

/ 在一固定容积为C的背包内装入N件物品, 物品的体积为:w1,w2,-----wn; 价值为:v1,v2,------vn; 求能装物品的最大价值。 / 这类问题的决策是:第N件物品放或者不放; 由此可以写出动态转移方程: 我们用n表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值 n*=max{n+v* , f} 注(j>=Wi); 这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为c的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题…

2012-07-07 16:22 · 程序设计 · 评论(0)

杭电1003代码

#include<stdio.h> int main() { int T,N,i,t=1,begin,end,max,min=1,sum,temp,n; scanf("%d",&T); while(T--) { scanf("%d",&N); begin=0; for(i=0;i<N;i++) { scanf("%d",&n*); if(i==0) max=n; else if(max<n*) { max=n*; begin=i; } } if(max<=0) { printf("Case %d:\n",t++); printf("%d %d %d",max,begin+1,begin+1)…

2012-07-07 10:24 · 程序设计 · 评论(0)