博文
动态规划之PKU1088(2006-06-24 15:15:00)
摘要：题目如下：（来源于http://acm.pku.edu.cn/JudgeOnline/problem?id=1088）
滑雪
DescriptionMichael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output输出最长区域的长度。
Sample Input5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output25
SourceDon't know
这是一道很简单的题，用DP很容易就AC了。
以下是我的代码：#include <iostream>
using namespace std;
int height[100][100],maxLen[100][100];
int row,col;
int maxLength(int i,int j)
{
if (maxLen[i][j] != 0)return maxLen[i][j];
int left,right,up,down,maxLR,maxUD;
left = right = up = down = 1;
if (j-1 >= 0)
if (height[i][j-1] >......
动态规划思想(2006-06-24 12:20:00)
摘要： 动态规划是解决一类包含了状态转化和状态转移关系，具有最优子问题性质的，求取状态参量的确定值或最优值的算法
动态规划，最简单的例子
o台阶问题
n某人上台阶，一次走1阶或者2阶 问从地面上至第n个台阶，共有多少种不同的走法？ 状态方程：f(n)=f(n-1)+f(n-2) 数列：1 1 2 3 5 8 13 21 34 55 89 144 233……
o程序：
int a[n]={1,1};
for(int i=2;i<n;++i)a[i]=a[i-1]+a[i-2];
动态规划，基本框架
1.1.划分给定问题为若干不同的阶段，并且用统一的方式表示出每个阶段的状态。
2.2.按照某种无后效性的规则选择状态。
3.确定状态决策和转移，更新状态列表。
4.3.是否已经遍历了整个状态空间？是则终止，否则转向步骤2
5.4.至此，状态列表中保存了所有的最优子问题的解。
......
回溯法解决N皇后问题(2006-06-22 12:37:00)
摘要：#include <iostream>using namespace std;
#define N 4
char board[N][N];int col[N]; //存储第i行对应的列的值，这样的(i,j)值满足当前棋盘上的皇后不能互相攻击。
bool safetyPlace(int x,int y) //(x,y)位置是否安全{ for (int i = 0; i < x; i++) { int j = col[i]; if (x == i || y == j)return false; //同一行或同一列 if (x-y == i-j || x+y == i+j)return false; //左，右对角线 } return true;}
void queen(int i) //处在第i行时状态{ if (i == N) //输出棋盘 {for (int w = 0;......
迷宫全部路径递归算法(2006-06-21 21:22:00)
摘要：#include <iostream>using namespace std;
#define N 4#define M 4
int x,y;enum direction{UP,DOWN,LEFT,RIGHT};
char Maze[N][M] = { '1','1','1','1', '1','1','0','1', '1','0','1','1', '1','1','1','1' }; bool visited[N][M]={false};
bool available(int i,int j){ if (i == -1 || i == N)return false; if (j == -1 || j == M)return false......
我的BLOG(2006-06-21 21:16:00)
摘要： 嘿嘿，又开通了一个BLOG。希望能通过这个平台认识更多的朋友，一起去算法的世界遨游。。。......