本文共 1566 字，大约阅读时间需要 5 分钟。

原题链接：

一：原题内容

Bean-eating is an interesting game, everyone owns an M*N matrix, which is filled with different qualities beans. Meantime, there is only one bean in any 1*1 grid. Now you want to eat the beans and collect the qualities, but everyone must obey by the following rules: if you eat the bean at the coordinate(x, y), you can’t eat the beans anyway at the coordinates listed (if exiting): (x, y-1), (x, y+1), and the both rows whose abscissas are x-1 and x+1.

Now, how much qualities can you eat and then get ?

4 611 0 7 5 13 978 4 81 6 22 41 40 9 34 16 1011 22 0 33 39 6

242

二：分析理解

《压缩元素，借助递推》
    首先，对于每一行，求出如果从这行挑元素（因为某个元素
被挑的话，它的上下行都不可以再被挑，而自身所在的那行还有
元素可以挑），可以得到的sum[i]，这样“就把这行m个数压缩为
一个元素了”；
    那么，对于n行都进行上面说的压缩（进行了n次），再竖着
这对着n个小sum进行一次同样的压缩，那么就得到了一个大SUM，
亦即ans。
分析转自：

三：AC代码

#include
   
      #include
    
     #include
     
        using namespace std;int a[200005];int b[200005];int main(){	int n, m, x;	while (~scanf("%d%d", &n, &m))	{		for (int i = 2; i <= n + 1; i++)		{			for (int j = 2; j <= m + 1; j++)			{				scanf("%d", &x);				a[j] = max(a[j - 1], a[j - 2] + x);			}			b[i] = max(b[i - 1], b[i - 2] + a[m + 1]);		}		printf("%d\n", b[n + 1]);	}	return 0;}
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/50953091 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！