<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
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. 
<div class='image'><a href='http://acm.hdu.edu.cn/data/images/convip1-1001-1.JPG' target='_blank' rel='noopener noreferrer'><img src="http://acm.hdu.edu.cn/data/images/convip1-1001-1.JPG" /></a></div>
Now, how much qualities can you eat and then get
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
There are a few cases. In each case, there are two integer M (row number) and N (column number). The next M lines each contain N integers, representing the qualities of the beans. We can make sure that the quality of bean isn't beyond 1000, and 1&lt;=M*N&lt;=200000.
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
For each case, you just output the MAX qualities you can eat and then get.
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
4 6 
11 0 7 5 13 9 
78 4 81 6 22 4 
1 40 9 34 16 10 
11 22 0 33 39 6
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
242
</blockquote>
</blockquote>
<h1 id="heading-1">翻译</h1>
<blockquote>
<h1 id="heading-2">背景</h1>
<blockquote>
吃豆子是一个有趣的游戏,每个人都拥有一个 <code>M</code> * <code>N</code> 矩阵,这里充满了不同质量豆子 
每个网格中只有一个豆子 
任务是收集最多的豆子 
但必须遵守以下规则: 
如果吃了坐标是 <code>(x,y)</code> 的豆子,则不能吃以下坐标的豆子(如果存在): 
<code>(x,y-1)</code> , <code>(x,y + 1)</code> ,横坐标为 <code>x - 1</code> , <code>x + 1</code> 的两行
</blockquote>
<h1 id="heading-3">输入</h1>
<blockquote>
多组数据输入 
每组数据先输入格数 <code>M</code> 、 <code>N</code> 分别代表 <code>M</code> 行 <code>N</code> 列 
接下来 <code>M</code> 行每行有 <code>N</code> 个数,代表这个格子豆子的质量 
豆子的质量小于 <code>1000</code> 
<code>1&lt;=N*M&lt;=200000</code>
</blockquote>
</blockquote>
<h1 id="heading-4">题解</h1>
<a href="/post/Algorithm/MUS.html">&gt;最大不连续子序列&lt;</a>
对于每一行,需要找出该行的最大不连续子序列 
记录下每行这个最大的值
再对于整个图,在每行的最大值中,找出最大不连续子序列 
此时求得的数,就是我们需要的答案
<h1 id="heading-5">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
using namespace std;

const int maxn = 200005;
int numt[maxn];
int num[maxn];
int dp[maxn];
int N,M;

bool Do() {
 if(scanf(&#34;%d%d&#34;,&amp;N,&amp;M) == EOF)
 return false;

 memset(dp,0,sizeof(dp));

 for(int i = 1;i &lt;= N;i++) {
 for(int j = 1;j &lt;= M;j++) {
 int temp;
 scanf(&#34;%d&#34;,&amp;temp);
 if(j &lt;= 2) {
 if(j == 1)
 numt[j] = temp;
 else
 numt[j] = max(numt[1],temp);
 } else {
 numt[j] = max(numt[j - 1],numt[j - 2] + temp);
 }
 }
 num[i] = numt[M];
 }

 dp[1] = num[1];
 dp[2] = max(num[1],num[2]);
 for(int i = 3;i &lt;= N;i++) {
 dp[i] = max(dp[i - 1],dp[i - 2] + num[i]);
 }

 printf(&#34;%d\n&#34;,dp[N]);
 return true;
}

int main() {
 while(Do());
 return 0;
}
</pre>

HDU 2845.Beans