记录编号	6250	评测结果	AAAAAAAAAA
题目名称	取数字问题	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2008-10-31 18:51:13	内存使用	4.15 MiB

#include <iostream>
#define MAX 21
#define Ran 21
#define Lim Ran*MAX*MAX
using namespace std;

int N,M,Ans;
int S[MAX][MAX];
bool F[MAX][MAX][Lim];

void init()
{
	int i,j;
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	cin >> N >> M;
	for (i=1;i<=N;i++)
		for (j=1;j<=M;j++)
		{
			cin >> S[i][j];
			S[i][j]+=10;
		}
	Ans=0x7FFFFFFF;
}

void dynamic()
{
	int i,j,k,l;
	F[1][1][ S[1][1] ]=true;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=M;j++)
		{
			for (k=0;k<Lim;k++)
			{
				l=k-S[i][j];
				if (l>=0)
				{
					if (i>1)
						F[i][j][k] |= F[i-1][j][l];
					if (j>1)
						F[i][j][k] |= F[i][j-1][l];
				}
			}
		}
	}
	for (i=11;i<Lim;i++)
	{
		if (F[N][M][i])
		{
			Ans=i-(N+M-1)*10;
			if (Ans>0)
				break;
		}
	}
}

int main()
{
	init();
	dynamic();
	cout << Ans << endl;
	return 0;
}