典型的动态规划。小意思。
/*
* File name : TestCPP.cpp
*
* Code by : IF
*
* Project name :
*
* Create datetime: 2011-02-22 06:53:22
*/
#include <iostream>
#include <time.h>
#include <assert.h>
using namespace std;
size_t TwoDToOneD(size_t column_num, size_t line, size_t column_index)
{
return line * column_num + column_index;
}
int Max(int a, int b)
{
return (a > b)?a:b;
}
int Calculate(size_t n, size_t m, int nums[]);
int main()
{
int *numbers = 0;
int n, m;
while (cin >> n >> m)
{
if (n * m <= 0)
{
break;
}
numbers = new int[n * m];
srand(time(NULL) );
for (size_t i = 0; i < n*m; i++)
{
numbers[i] = rand() % 10;
}
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j< m; j++)
{
cout << numbers[TwoDToOneD(m, i, j)] << " ";
}
cout << endl;
}
cout << Calculate(n, m, numbers) << endl;
delete []numbers;
}
return 0;
}
// n行 m列
int Calculate(size_t n, size_t m, int nums[])
{
int result = 0;
int *max_sums = new int[n * m];
assert(max_sums);
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < m; j++)
{
max_sums[TwoDToOneD(m, i, j)] = nums[TwoDToOneD(m, i, j)];
if (0 == i + j)
{
continue;
}
if (0 == i)
{
max_sums[TwoDToOneD(m, i, j)] += max_sums[TwoDToOneD(m, i, j - 1)];
continue;
}
if (0 == j)
{
max_sums[TwoDToOneD(m, i, j)] += max_sums[TwoDToOneD(m, i - 1, j)];
continue;
}
max_sums[TwoDToOneD(m, i, j)] += Max(max_sums[TwoDToOneD(m, i, j - 1)], max_sums[TwoDToOneD(m, i - 1, j)]);
}
}
result = max_sums[TwoDToOneD(m, n-1, m-1)];
delete []max_sums;
return result;
}
温馨提示:答案为网友推荐,仅供参考