聪明的kk

聪明的kk

时间限制：1000 ms  |  内存限制：65535 KB

描写叙述

聪明的“KK”
非洲某国展馆的设计灵感源于富有传奇色彩的沙漠中陡然起伏的沙丘。体现出本国不断变换和绚丽多彩的自然风光与城市风貌。展馆由五部分组成，馆内影院播放名为《一眨眼的瞬间》的宽银幕短片。反映了建国以来人民生活水平和城市居住环境的惊人巨变。
可移动“沙丘”变戏法 的灵感源于其独特而宏伟的自然景观——富于传奇色彩的险峻沙丘。宏伟的结构、可循环的建材，与大自然相得益彰。围绕一周，发现它正是从沙丘那不断变换的形态中汲取灵感的。外形逼真到不管从哪个角度去观察，都能清楚地辨识出沙丘的特征。
它“坡面”高达20米，微风吹来。你是否感觉到沙的流动？用手去触碰，却发现原来是“魔术戏法”。它表面的不锈钢面板呈现出一种富于变幻的色彩。从不同角度观察，呈现不同色泽。由此来模仿流动沙丘的光感。
走进第三展厅有一个超大的屏幕，通过奇异的特效，让观众宛如亲身来到浩瀚的沙漠。

更为奇异的是，仅仅见一个小动物“KK”正从沙漠区域（矩形）的左上角沿着向右或向下的方向往右下角跑去。

KK太聪明了，它竟然能在跑的过程中会选择吃掉尽可能多的虫子线路。
你知道它吃掉多少虫子吗？

输入

第一行：N M (1≤N M≤20 0≤Xij≤500(i=1,2„.N, j=1,2„,M)
)表示沙漠是一个N*M的矩形区域
接下来有N行：每行有M个正整数，Xi1 Xi2 ……Xim 表示各位置中的虫子数（单个空格隔开）
如果“KK”仅仅能向右走或向下走。

输出

输出有一个整数， 表示“KK”吃掉最多的虫子数。

例子输入

3 4
3 1 2 8
5 3 4 6
1 0 2 3

例子输出

24

来源

第三届河南省程序设计大赛

上传者

苗栋栋

思路：这个题之前就见过，就是不知道怎么求到最大的吃到虫子的数量。

看了以下的百度文库写的，受益匪浅。。

就是再构造一个sum数组。里面存放的每个元素。都是相对来说吃到的虫子个数最多的，我是这样觉得的。

当然也能够把这条最大吃虫路线得出来。

。写个标志即可了。

參考文库：http://wenku.baidu.com/link?url=hY9UjzvYXfwZuxcfYkfeKzuiHYNaMdjeKCUqByXGNMBU0ngukfjiLrCcKK5XSn63CAy56LSBVrOGYxop-a-h1OXq3d8McZNe7MgyNeciZUW

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
	int N,M,i,j,a[20][20],sum[20][20];
	memset(sum,0,sizeof(sum));
	cin>>N>>M;
	for(i=0;i<N;i++)
		for(j=0;j<M;j++)
			cin>>a[i][j];
		sum[0][0]=a[0][0];	
    for(i=1;i<N;i++)
		sum[i][0]=sum[i-1][0]+a[i][0];
	for(i=1;i<M;i++)
		sum[0][i]=sum[0][i-1]+a[0][i];
	
    for(i=1;i<N;i++)
	{
		for(j=1;j<M;j++)
		{
			if(sum[i-1][j]<sum[i][j-1])
				sum[i][j]=a[i][j]+sum[i][j-1];
			else
			    sum[i][j]=a[i][j]+sum[i-1][j];
		}
	}
	cout<<sum[N-1][M-1]<<endl;
	return 0;
}