更新:2014-02-08 凌晨
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
来源:http://acm.fzu.edu.cn/problem.php?pid=1004
概述:给一个数值金字塔,问从上往下,怎么走,路过的数求和最大。
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
分析
估计是“讹传讹”,网上散布的大部分解法,都是金字塔从下往上加,且用二维数组存储。我本来是用单维数组来存储,比较节省内存。后来发现这题其实有很简洁的解法。
动态规划,可以边导入数据边运算,在每一行,都更新为从第一行到该点的最优解值。最后判断最后一行中的最大值即可。
这题的一种简单变形是改成求和的最小值,只要把18行的函数换成__min即可,注意用VC++提交,只有VC在<cstdlib>才有__max,__min宏定义。
#include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; int main() { int n, i, j, now; while (scanf("%d", &n) != EOF) { int a[2][1001] = {0}; for (now = i = 1; i <= n; i++) { now ^= 1; for (j = 1; j <= i; j++) { scanf("%d", &a[now][j]); a[now][j] += __max(a[now^1][j-1], a[now^1][j]); } } printf("%d\n", *max_element(&a[now][1], &a[now][n+1])); } return 0; }