文章列表
动态规划算法
一、基本概念
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
二、基本思 ...
题目链接：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 result ...
题目
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的矩阵表示两个城市之间的安全系数， ...
题目描述：
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 suppo ...
这道题主要就是判断一下有没有环，还有就是节点数减去边数等于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来走。但是她设计迷宫的思 ...
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<=10 ...
迪杰斯特拉算法
迪杰斯特拉(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的路径权值之和 ...
开启windows 7的隐藏功能：虚拟WiFi和SoftAP（即虚拟无线AP），就可以让电脑变成无线路由器，实现共享上网。
点开始 所有程序 命令提示符右键管理员身份运行命令提示符 运行命令：netsh wlan set hostednetwork mode=allow ssid=wuminPC key=wuminWiFi
此命令有三个参数，mode：是否启用虚拟WiFi网卡，改为disallow则为禁用 。 ssid：无线网名称，最好用英文(以wuminPC为例)。 key：无线网密码，八个以上字符(以wuminWiFi为例)。
以上三个参数可 ...
杭电acm部分题目分类
- 博客分类：
- 程序设计
注：DP代表动态规划
1001 这个就不用说了吧
1002 简单的大数
1003 DP经典问题，最大连续子段和
1004 简单题
1005 找规律（循环点）
1006 感觉有点BT的题，我到现在还没过
1007 经典问题，最近点对问题，用分治
1008 简单题
1009 贪心
1010 搜索题，剪枝很关键
1011
1012 简单题
1013 简单题（有个小陷阱）
1014 简单题
1015 ...
/*在一固定容积为C的背包内装入N件物品，
物品的体积为：w1,w2,-----wn;
价值为：v1,v2,------vn;
求能装物品的最大价值。*/
这类问题的决策是：第N件物品放或者不放；
由此可以写出动态转移方程：
我们用n[i,j]表示在前 i 件物品中选择若干件放在所剩空间为 j 的背包里所能获得的最大价值
n[i][j]=max{n[i-1][j-Wi]+v[i] , f[i-1,j]} 注(j>=Wi)；
这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为c的背包中” ...