矩阵连乘
【代码】 #include #include #define N 100 int m[N][N]; //m[i][j]表示从第i个矩阵连乘到第j个矩阵的最小计算次数 int s[N][N]; //第i个矩阵连乘到第j个矩阵时在何处断开，用于构造最优解 int p[N]; //表示矩阵i为p[i-1]×p[i] void MatrixChain(int n) …
CODE, ARCHITECTURE & AI
动态规划.
晴天小猪历险记之Hill
在很久很久以前，有一个动物村庄，那里是猪的乐园（^_^），村民们勤劳、勇敢、善良、团结…… 不过有一天，最小的小小猪生病了，而这种病是极其罕见的，因此大家都没有储存这种药物。所以晴天小猪自告奋勇，要去采取这种药草。于是，晴天小猪的传奇故事便由此展开…… 【描述 Description】 这一天，他来到了一座深山的山脚下，因为只有这座深山中的一位隐者才知道这种…
邮局问题 vijos1242(和以前的pku上的应该是一样的.)
/* 动态规划。 将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为a[1..n]， 状态表示描述为：f[i,j]表示在前i个村庄建立j个邮局的最小距离和。所以，f[n,p]即为问题的解， 且状态转移方程和边界条件为： f[j,1]=w[1,j]; f[i,j]=min{f[k,j - 1]+w[k+1,i]}; (i≤j, j - 1≤k≤i…
Post Office pku1160 邮局
package pku1160; /*在一条高速公路边上有V个村庄，用一条坐标轴来描述这条公路，每个村庄的坐标各不相同， * 且都是整数。两个村庄间的距离用他们的坐标值差的绝对值表示。现在要在这些村庄中选 * 出P个建立邮局，邮局建立在村庄里，每个村庄使用离他最近的那个邮局。求一种建设方案， * 使得所有村庄到各自所使用的邮局的距离总和最小。 * * 算法:…
合唱队形
【问题描述】 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<... Ti+1>…>TK(1<=i<=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下…
滑雪 pku1088 动态规划
【Description】 Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25…
青蛙过河
【描述】 在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距…