聪明的kk（动态规划）

聪明的kk

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

难度：3

描述

聪明的“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

   思路：

   考虑每个数的来源，第一行和第一列每个数的来源只有一个，所以第一行与第一列每个数都是一个可以确定的数。然后从中间的元素开始看，每个来源有两个，这时候要使终点值最大，那么应该途中的每个数都应该以最大的条件来考虑，所以两个数来源应取用大的那个数，最后得出来的终点值就是最大的了。

 

   例子如表格所示：

3	1+3=4	2+4=6	8+6=14
5+3=8	3+8=11	4+11=15	6+15=21
1+8=9	0+11=11	2+15=17	3+21=24

    AC：

#include<stdio.h>
int main()
{
	int n,m,i,j;
	int number[25][25];
	int sum[25][25];
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	  scanf("%d",&number[i][j]);
	
//	printf("\n");
//	for(i=1;i<=n;i++)
//	 {
//	  for(j=1;j<=m;j++)
//	   printf("%d ",number[i][j]);
//      printf("\n");
//       }
	 
	 sum[1][1]=number[1][1];
	 for(i=2;i<=n;i++)
	   sum[i][1]=number[i][1]+sum[i-1][1];
	 for(i=2;i<=m;i++)
	   sum[1][i]=number[1][i]+sum[1][i-1];
//对只有一个来源的第一行第一列元素进行计算赋值
	 for(i=2;i<=n;i++)
	  for(j=2;j<=m;j++)
	  {
	    if(sum[i][j-1]>sum[i-1][j]) sum[i][j]=number[i][j]+sum[i][j-1];
	    else sum[i][j]=number[i][j]+sum[i-1][j];
	  }
//对有两个来源的元素进行对比加和  
	printf("%d\n",sum[n][m]); 
	return 0;
}

   最优解法：

#include<iostream>
using namespace std;
int f[22][22];
int main()
{
   int n,m,c;
   cin>>m>>n;
  for(int i=1;i<=m;i++)
    for(int j=1;j<=n;j++)
      {
       cin>>c;
       f[i][j]=max(f[i][j-1],f[i-1][j])+c;
//设当时状态为第i行，第j列
//所以要此时这点的值最大，那么应加上它的左边f[i][j-1]或者上边f[i-1][j]的最大值才对，而当时处在这个位置的值也需要加上
//无论如何处在这个位置的值都是一定要加上的
      }
  cout<<f[m][n]<<endl;
}

   

   总结：

   看完NYOJ给出的最优解法，真的有想一头撞死的冲动，f[i][j]=max(f[i][j-1],f[i-1][j])+c，其实就是题目给出的两个条件来源……想得太过复杂了，跟之前动态规划的例题很相似，但是那题的终点是不确定的，然后想到了这题的终点是确定的。还有，想到边界的情况应该怎么算才对，其实第0行和第0列也可以当成是来源，因为值是0没有根本影响……而且不需要另外开个数组来保存处在每个位置的值，每次比较完后加上就对了，因为这个值是一定要加上的。当循环完N行M列后，最后得出来的f[N][M]也是最大的，并且其他每个格子都是在该位置值最大的时候，因为各个最优才是全局最优。