pku1157.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 46 行

#include <stdio.h>
#include <string.h>
#define size 110

int val[size][size];
int bst[size][size];
int F, V;

int Max(int a, int b)
{
	return a > b ? a : b;
}

int Solve()
{
	int i, j;
	memset(val, 0, sizeof(val));
	memset(bst, 0, sizeof(bst));
	for (i = 1; i <= F; i++)
	{
		for (j = 1; j <= V; j++)
		{
			scanf("%d", &val[i][j]);
		}
	}
	for (i = 1; i <= V; i++)
	{
		bst[i][i] = bst[i - 1][i - 1] + val[i][i];
	}
	for (i = 1; i <= V; i++)
	{
		for (j = 1; j < i; j++)
		{
			bst[i][j] = Max(bst[i - 1][j - 1] + val[j][i], bst[i - 1][j]);
		}
	}
	printf("%d\n", bst[V][F]);
}

int main()
{
	while (EOF != scanf("%d %d", &F, &V))
		Solve();
	return 0;
}