加载中…数塔问题，简单的动态规划算法
(2012-07-12 15:19:10)
标签：
杂谈 |
- 数塔问题：
- 9
- 12 15
- 10 6 8
- 2 18 9 5
- 19 7 10 4 16
- 有形如图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，
- 一直走到底层，要求找出一条路径，使路径上的值最大。
- 这道题如果用枚举法，在数塔层数稍大的情况下（如40），则需要列举出的路径条数将是一个非常庞大的数目。
- 如果用贪心法又往往得不到最优解。
- 在用动态规划考虑数塔问题时可以自顶向下的分析，自底向上的计算。
- 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，
- 只要左右两道路径上的最大值求出来了才能作出决策。
- 同样的道理下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。
- 这样一层一层推下去，直到倒数第二层时就非常明了。
- 如数字2，只要选择它下面较大值的结点19前进就可以了。
- 所以实际求解时，可从底层开始，层层递进，最后得到最大值。
- 总结：此题是最为基础的动态规划题目，阶段、状态的划分一目了然。
- 而决策的记录，充分体现了动态规划即“记忆化搜索”的本质。
- */
- #include <iostream>
- #define MAX 20
- using namespace std;
- int main()
- {
- cout << "Please input N(lines)" << endl;
- int n;
- cin >> n;
- int a[MAX+1][MAX+1][3]; //[0]用来存数，[1]参与运算，[2]表示向左(0)，还是向右(1)
- //输入数塔
- for(int i = 1; i <= n; ++i)
- {
- cout << "Please input line " << i << endl;
- for(int j = 1; j <= i; ++j) //第i行有i个数
- {
- cin >> a[i][j][0];
- a[i][j][1] = a[i][j][0];
- a[i][j][2] = 0;
- }
- }
- cout << endl;
- //计算
- for(int i = n-1; i >= 1; --i) //从倒数第二行开始
- {
- for(int j=1; j <= i; j++)
- {
- if (a[i+1][j][1] > a[i+1][j+1][1]) //左边大
- {
- a[i][j][2] = 0; //选择左边
- a[i][j][1] += a[i+1][j][1];
- }
- else //右边大
- {
- a[i][j][2] = 1; //选择右边
- a[i][j][1] += a[i+1][j+1][1];
- }
- }
- }
- //输出数塔
- for(int i = 1; i <= n; ++i)
- {
- for(int j = 1; j <= i; ++j)
- {
- cout << a[i][j][0] << " ";
- }
- cout << endl;
- }
- //输出最大值
- cout << a[1][1][1] << endl;
- //输出路径
- for(int i = 1, j = 1; i<= n; ++i)
- {
- cout << "[" << i << "," << j << "]" << " -> ";
- j += a[i][j][2];
- }
- cout << endl;
- return 0;
- }
免费馅饼
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 13392 Accepted Submission(s):
4418
为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。
代码如下：
#include<iostream>
#include <algorithm>
using namespace std;
inline int Max(int a, int b, int c=-1)
{
}
int dp[11][100001];
int n;
int main()
{
}
喜欢
0
赠金笔