数字金字塔 Time Limit:1000MS  Memory Limit:65536K Total Submit:394 Accepted:225 Description 你和权权是一对很好很好的朋友。有一天，你们无聊得很，便上网冲浪，突然在一个叫做USACO的网中找到了一个游戏：《数字金子塔》。游戏规则是这样的：求一个数字金字塔中从最高点开始在底部任意处结束的路径经过数字的和的最

题意 在规定的时间内，可以采到的草药的最大总价值。 分析 设 f[i,j]表示前i件物品，总重量不超过j的最优价值 则 f[i，j]=max{f[i－1，j-w[i]]+P[i]，f[i－1，j]）（1<=i<=m,1<=j<=t,j>=w[i]）顺推 F[m,t]即为最优解 var t,m,i,j:longint; w:array[1..1000]of longin

题意 在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。 分析 设 f[i,j]表示前i件物品，总重量不超过j的最优价值 则 f[i，j]=max{f[i－1，j-w[i]]+P[i]*v[i]，f[i－1，j]）（1<=i<=m,1<=j<=n,j>=w[i]）顺推 F[m,n]即为最优解 var n,m,i,j:longint;

题意 写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 分析 f[j] 表示第i行第j个位置上的数到顶点的最大值。 F[j]=max{a[j]+f[j-1],a[j]+f[j]}2<=j<i F[1]=a[1]+f[1] var n,i,j,w:longint; a,f:array[1..10000]

题意 写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 分析 这题我是用顺推法来做的 按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和,再依次求出第3,4，5,......,.n-1,n到起点的最大和,最后找第n行的最大值设f[i,j]为第i行第j列