#include<iostream>

using namespace std;

#define MAX 100
int row,column;
int a[MAX][MAX],sum[MAX][MAX];

int FindMaxSum(int x , int y)
{
	if(sum[x][y] > 0) return sum[x][y];
	if(x == row - 1)
	{
		sum[x][y] = a[x][y];
		for(int i = y; i < column; i++)
		{
			if(sum[x][y] < a[x][i])	sum[x][y] = a[x][i];
		}
		return sum[x][y];
	}
	for(int j = y; j < column - row + x + 1; j++)
	{
		int temp = a[x][j] + FindMaxSum(x + 1,j + 1);
		if(sum[x][y] < temp) sum[x][y] = temp;
	}
	return sum[x][y];
}

int main()
{
	int i,j;
	while(scanf("%d%d",&row,&column) != EOF)
	{
		for(i = 0; i < row; i++)
			for(j = 0; j < column; j++)
				scanf("%d",&a[i][j]);
		memset(sum,0,sizeof(sum));

		

		printf("%d\n",FindMaxSum(0,0));
	}
	return 1;
}



是不是不能用递归结构写？
不过我感觉这道题拿递归写思路慢清晰的，而且也没有什么太大负面影响～

谁能指教一下？～
谢谢了

• 最优方案也可能是负的 (56) twilight 2008-05-30 13:11:52